How do you learn dynamic programming?

When I think back to learning dynamic programming, it was really hard. Dynamic programming is really difficult, testing logical thinking ability, abstraction ability, and mathematical modeling ability. But is it really so hard to get started with dynamic programming? I think it is really not difficult, is simply looking for rules; Here I want to help you understand dynamic programming in a more wild way, this method is really very simple and effective, god please ignore.

DP table

What method? Just draw a chart and look for patterns. This method is very effective in many problems, especially matrix DP, it is a panacea; This method is very simple, you only need to remember two techniques.

  1. Make the problem smaller and think about it in smaller ways
  2. Fill in the form according to the small questions and find the pattern

With these two skills in mind, let me explain a relatively simple, a slightly more difficult real problem.

62. Different paths

  • Do not simply think, pure thinking will waste a lot of time, or even at a loss, do not know how to do, directly draw a table to find rules, here I use a 5*7 table for example.

  • First of all, why is the first row and the first column all 1’s? Because if there’s only row one column one, there’s only one way for the robot to go.
  • Recall the two tips above; Let’s say we make the grid smaller, so we make the problem smaller, a 3 by 3 table.
  • How many ways can I do 3 times 3? Just fill out the form and you’ll get the answer. The answer is six.
  • Why six? Because the robot can only go to the right or down, to the bottom right corner of 3 by 3, it can only go up or down, or to the left.
  • What if I made it even bigger, like a 4 by 4 table? We continue to fill in the form

  • Looking at the answer, the answer is 20; What’s the pattern? I’m sure there’s no one who can’t see this pattern, right?
  • Obviously, table[3][3] = table[2][3] + table[3][2], that is to say, there are 20 ways for the robot to go to the bottom right corner of the grid of size 4 * 4.

Write the code

At this point, I’m sure it shouldn’t be hard to write code?

var uniquePaths = function (m, n) {
  // Because the first row and first column are all 1's
  let dp = Array.from(new Array(m), () => new Array(n).fill(1))
  for(let i = 1; i < m; i++){
    for(let j = 1; j < n; j++){
      Dp [I][j] + dp[I][j-1]
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]};Copy the code

In fact, dynamic programming is so simple, is simply draw tables to find rules.

1143. Longest common subsequence

  • Let’s analyze the problem. Let’s find the longest common subsequence of two strings. Just draw a chart and observe the pattern

  1. Why are there empty strings? Why do empty strings correspond to 0’s? You think, need to derive the answer from nothing, find out the rule, so need to use empty string; If one of these strings is empty, they must both be 0.
  2. Because the answer to the use case is 3, so I’m going to put the result up first, so I can use that result to figure out the pattern.
  3. Let’s go ahead and fill out the table and figure out the pattern.

  • Text1 [0] == Text2 [0] when the size of the problem becomes larger, the answer is clearly 1. So here we see that we have to increase by 1 for equality. Good boy, keep watching.

  • Text1 [0] == the row and column of text2[0]. Because as text1/text2 gets longer and longer, does that affect the final result? Obviously, it doesn’t. Keep filling out the forms and looking for patterns.

  • When we say text1[I] == text2[j], it must increment by 1, but on what basis? When the size of the problem is obviously smaller, that is, when there is no character C, that is, the table[1][2], the green area of the block 1.
  • So let’s keep filling out the form. Let’s look at the red block.

  • Finally, the answer is verified. When two characters are equal, it is equal to the previous small problem plus 1. If you do not want to wait, it is the same as if there is no character. I’m just going to take the maximum of two strings with one missing.
  • So here’s the rule:
  1. text1[i] == text2[j], table[i][j] = table[i – 1][j – 1] + 1
  2. text1[i] ! = text2[j], table[i][j] = max(table[i – 1][j], table[i][j – 1])

Write the code

var longestCommonSubsequence = function(text1, text2) {
  let n = text1.length
  let m = text2.length
  let dp = Array.from(Array(n + 1), () = >Array(m + 1).fill(0))
  // the null string is 0,0
  for(let i = 1; i <= n; i++){
    for(let j = 1; j <= m; j++){
      if(text2[j - 1] == text1[i - 1]){
         dp[i][j] = dp[i - 1][j - 1] + 1
      }else{
         dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])}}}return dp[n][m]
};
Copy the code

conclusion

In fact, this way to write dynamic programming is very wild way, but for beginners, it is really good to get started. Dynamic programming is indeed a bit difficult, and it is not easy to explain it clearly. I hope this article on hydrology can help you better understand dynamic programming. Internet people are encouraged ~