Dynamic Programming (EN) | 动态规划-从入门到劝退

INTRO: After school ends, I start to solve dynamic programming problems. After I look up the four dynamic problems posted by my brilliant friend, in which she wrote a general solution to each of them in an article, I feel it’s a good time for me to dive into the topic. Not surprisingly, my attempt to solve the first one failed gracefully. So I scratched my head and decided to learn everything from the very beginning. I have no prior dynamic programming knowledge and the concept usually confuses a lot of people including me. After another day of looking up a simpler dynamic programming problem, I finally am able to understand and solve the first problem in her article. Hopefully, by writing this post I would be able to consolidate the concepts and it would be great if other people would also be able to benefit from it…or not… (Long journey ahead…sigh…)

Knowledge required before you dive into the topic: Binary Tree, Node, 2D Array, Recursion

Just like AI is nothing more than a fancy curve fitting, DP is nothing more than a fancy grid manipulation – said by me.

Lv.1 - Maximum Path Sum in a Triangle (LeetCode 120 for Minimizing Triangle)

Probably one of the easiest dynamic programming problem to start with that also helps to demystify dynamic programming.

Description: Given numbers in form of triangle, by starting at the top of the triangle and moving to adjacent numbers on the row below, find the maximum total from top to bottom. You can go either left or right in each step.

Example:

At first glance, it might gives you a headache to think about how to solve it from the top point. It seems that I should choose 7 in our first step, but soon you realize that what if that 6 in the third level is a very big number? In that case going left doesn’t seem to be a very good decision, because by choosing it to go left, you could potentially miss a super big number to the right part of the triangle.

It seems that you couldn’t decide which way to go unless you know which way is the best way to go. Wait, before you feel that you’ve got into a Mobius strip, it almost sounds like a recursive question! What if I can know which way is the best way to go? All I need to do is to start from the bottom.

The so called Bottom-Up approach - If I could know at the very bottom child (left or right) has the maximum number, then we could just simply add that maximum child to its parent node to get the maximum number we want for the previous level.

How I get 13: Compare the children (5 and 9) of 4 in the third level, 9 is the greater one, add that number to the parent node 4 to get 13 in the previous level.
How I get 19: After the third level iteration is completed, Iterate the nodes in second level. For the 4 in the second level, I compare its updated children 13 and 15, and add 4 to 15 (the bigger one) to get 19.
How to get the rest: Your Turn.

After you figured out the logic, the code is simple: All you need to do is to compare the children from bottom to top, take the greater one, add that to the parent node. Then we can use the updated parent nodes as the children for their previous level.

1
2
3
4
5
6
7
8
9
def maxSumPath(arr):
dp = arr
for i in range(len(arr)-2,-1,-1):
for j in range(0, i+1):
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + dp[i][j]
return dp[0][0]

print(maxSumPath([[3,0,0,0],[7,4,0,0],[2,4,6,0],[8,5,9,3]]))

LeetCode 120 : All you need to do is to change the max to min to solve this problem.

Some observations:
O1: DP is kinda like an advanced recursion - and most of the time you can use recursion to solve a dp problem, if not consider time and space constraints. Just that dp uses a more rigorous logic to solve the problem more efficiently.
O2: Solving the subproblem leads you solve the bigger problem.
O3: We are not remembering the exact path that gives the best result, this information is lost.
O4: Don’t be fooled by the name dp, it can be named as anything and it’s just a grid that hold useful information. (We will get into the terminology of states later).

Lv.2 - Longest Common Subsequence (LeetCode 1143)

Note: This problem further reinforce the idea that learning computer science is less about learning how to code but more about understanding the logic behind it. (This problem also reminds me about squeeze theorem for some reason…). This problem would also introduce a more complicated idea behind “grid making”.

Description: Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

Example:

Strategy 1: What could be the sub problems?

Notation: S1 and S2 corresponds to sentence 1 and sentence 2. S1(i-1) represents the whole sentence minus 1 character in the very end, same for S2. However, we use i and j instead of the String length because we want this notation to represents the same thing for all substring in S1 and S2. For example, the substring pair “abcd” and “ac” from the original pair “abcde” and “ace”.

Thinking Process: It might be intuitive to think that - if I know the Longest Common Subsequence for S1(i-1) and S2(j-1), then if the next character is the same, I would intuitively know that the LCS for S1(i) and S2(j) is going to be LCS(S1(i-1), S2(j-1)) + 1. But what if they’re not the same? What kind of substring can we infer?

Let’s do an example using S1 = “abcde” and S2 = “ace”.

Starting from the very end, if we already know the LCS for S1(i-1) and S2(j-1) (in this case, S1(i-1) equals “abcd” and S2(j-1)equals “ac”), then if we compare the last letter which is “e”, we would know that the LCS is just LSC(S1(i-1), S2(j-1)) + 1. This is the intuitive part. Here is the tricky part, if the last letters are not equal, it does NOT necessarily mean that the LCS for LSC(S1(i), S2(j)) is just LSC(S1(i-1), S2(j-1)).

For example, taking the 2 substring from the example: “abcd” and “ac”. We know that the LCS for “abc” and “a”, which corresponds to a local LSC(S1(i-1),S1(j-1)), is 1. Since the last letter for “abcd” and “ac” is not the same, we might naively assume that the LCS(S1(i), S2(j)) is 1, but in fact it’s 2. What went wrong? – It’s because it’s possible that even if the last letters didn’t match with each other, the new letter from one string might match the second-to-last letter of another string. Since it goes two ways, LCS(S1(i), S2(j)) when the last letter does not match with each other should be the greater of LCS(S1(i-1), S2(j)) and LCS(S1(i), S2(j-1)). Note that we don’t need to worry about “what if that new letter matches the third or fourth-to-last letter of another string. That has already been taken cared by solving the sub-problems.

Strategy 2: Draw a grid that solves all the sub problems first then observe the pattern.

Here is another different way to approach this problem: You still need to think about sub problems but you could think a very intuitive one with brute force thinking, but a slightly smarter one - What if I could find the LCS for all the combinations for the two strings? Would that leads me to somewhere? Sure, I’m a visual person and lazy and I like to solve problems by finding “short cut”. Eventually though, you still need to put some brain power to find the logic behind your observation to back it up, but it’s a place to start.

Starting from drawing a grid that contains the LCS for all substrings:

Then label the LCS for each combination: (Remember to padding the first row and first column to 0, as a single string with an empty string has a LCS of 0)

And you would discover the same thing as I stated in the first strategy. In fact, one way to think about dynamic programming is that it lays out all the possible states a problem can have, and observe the relationship between the states. The algorithm is an implementation that transforms the states from the source to the goal, based on the rules you observed. Again, the algorithm is simple as it’s just a manipulation of the values (or aka the “state”) in the grid (You only need to know how to manipulate 2D array to do it). The core is about finding all possible states and their relationships among themselves.

Python Implementation for LeetCode 1143 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
len1=len(text1)+1
len2=len(text2)+1
dp = [[None for j in range(len2)] for i in range(len1)]
for i in range(len1):
dp[i][0]=0
for j in range(len2):
dp[0][j]=0
for i in range(1,len1):
for j in range(1,len2):
if(text1[i-1]==text2[j-1]):
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i][j-1],dp[i-1][j])
return dp[len1-1][len2-1]

Lv.3 Split Array Largest Sum (LeetCode 410)

Note: This is also the first question in my friend’s article.

Description: Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Example:

After completed two DP problems, you might still feeling a little bit shaky about solving other problems, after all, there’s no deterministic formula for DP problems. Every DP formula is different problem by problem. But it’s kind of getting to your gut that first, finding all the possible states feels important, second, we need to logic out what would be the relationship among the states and transfer the start state to end state.

Q1: What are the states (sub-problems)? If I have an array of [7,2,5,10,8] with m = 2, it means that I need to think about all the possibilities from m = 1 to m = 2 for each subarray in the original array. (Notice that there’s no m = 0 because there cannot be such a thing as having a 0 number of subarrays, be careful about the index). Just like the following grid: We could hand-calculate those values rather effortlessly.

Q2: But that just seem to me like random numbers, let’s zoom in a little bit. The first row is easier to understand: if we are only asked about one subarray, then the answer would just be the sum of all numbers in the original array. How about second row? The first 7 also makes sense because if the number of m and n are equal, then the answer would be the max number in the original array. But it didn’t tell too much interesting story about all other numbers, for example, how did we get the second 7 in the second row?

Now hold back a little bit, what does it mean if we know the optimal solution for [7] and [7,2] in the first row? How about [7,2] in the second row? Start with the number [7,2] in the second row, this number gives us the optimal solution when there are two subarrays for [7,2]. Would this information be helpful for us to derive the optimal solution when there need to be two subarrays for [7,2,5]? Not really. After thinking about it carefully, the arrangement for [7,2,5] can be [7,2] and [5] OR [7], [2,5], and the optimal answer can in either arrangement. In other words, the optimal solution in A(i-1) in the same row did not help us to reduce the calculation for us to decide the optimal solution in A(i).

How about the optimal solution for [7] and [7,2] in the first row? What does it mean that we know the optimal solution from A(0) to A(i-1)? How are they relevant to the optimal solution for A(i)? Actually, we are on the right track. When an additional number kicks in at the second row at [7,2,5], it can be either divided into [7] and [2,5] OR [7,2] and [5]. And if we know the best way to divide [7] and [7,2] in the first row, all we need to do is to iterate through both cell, subtract the array sum by 7 and 9 respectively, compare the pairs, and take the minium of the pairs’ maximum: min(max(7,14-7), max(9, 14-9)), which gives you the answer 7 for [7,2,5] in the second row.

Putting everything into logic:

$dp[i][j] = min(dp[i][j], max(dp[i-1][x], sums[j]-sums[x]))$ for x in range (i, j).

Python Implementation for LeetCode 410 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def splitArray(self, nums: List[int], m: int) -> int:
m = m-1
row = m+1
col = len(nums)+1
# Avoid repeated calculation by adding sums up
sums=[0]*col
for i in range(1,col):
sums[i]=sums[i-1]+nums[i-1]
for j in range(1,col):
dp[0][j] = sums[j]

# Dynamic Programming Part. The first two loops represents dp[i][j], the third loop represents the summation I stated above.
dp = [[math.inf for j in range(len(nums)+1)]for i in range(m+1)]
dp[0][0]=0
for i in range(1,row):
for j in range(i,col):
for k in range(i,j):
dp[i][j]=min(dp[i][j], max(dp[i-1][k], sums[j]-sums[k]))

return dp[row-1][col-1]

Note: There is also a genius way to solve this problem using binary search, please see here.

  • © 2020-2021 Yingru Qiu
  • Powered by Hexo Theme Ayer
  • PV: UV: