# A brief introduction to dynamic programming Dynamic programming is a way to find the optimal solution, and my personal understanding is not very deep. I write randomly, it is a little bit of my own understanding, and criticism is welcome if there is anything wrong. Dynamic programming is a way of deriving the next optimal state from the previous optimal state when transitioning between multiple states, and the previous optimal state is derived from the previous optimal state, so Keep moving forward, and finally we only need to know the initial optimal state. Through the initial optimal state and the logic and method of transition between states, we can obtain the global optimal state. (Does it feel a bit like mathematical induction?)

To give an example of the Fibonacci sequence, the easiest solution is to use recursion.

 ` 1 2 3 4 5 6` ` def fab (n) : if n == 0 : return 0 if n == 1 : return 1 return fab(n - 1 ) + fab(n - 2 )`

A simple analysis shows that in the above example, many numbers are counted repeatedly. For example, `fab(3)` `fab(5)` ) is calculated, but `fab(3)` `fab(4)` calculated. Therefore, we can use a table to save the already calculated data to avoid repeated calculations

 ` 1 2 3 4 5 6 7 8 9 10 11 12` ` table = {} def fab (n) : if n in table: return table[n] if n == 0 : result = 0 elif n == 1 : result = 1 else : result = fab(n - 1 ) + fab(n - 2 ) table[n] = result return result`

After changing the strategy, we found that the calculation speed is much faster, which is actually the overlapping sub-problems that dynamic programming needs to avoid. The existence of these overlapping sub-problems leads to a lot of extra computation if brute force exhaustion is used. The solution of dynamic programming is to find the optimal substructure , and finally obtain the optimal solution by continuously performing state transitions between the optimal substructures, and this state transition logic is called the state transition equation .

Observing again, you can know that the calculation of the Fibonacci sequence only depends on the first two values ​​of the current value, so we do not need to use a table to store data, but only need to store two previous value variables.

 ` 1 2 3 4 5 6 7 8 9 10 11 12` ` def fab (n) : if n == 0 : return 0 if n == 1 : return 1 a = 0 b = 1 for i in range( 2 , n + 1 ): tmp = a + b a = b b = tmp return b`

From the above, we can know that, in fact, the calculation process of the Fibonacci sequence is a process of using the optimal substructure, state transition equation and initial state to finally obtain the global optimal solution. Let’s look at another example of jumping stairs

There is a stair, you can jump 1 step or 2 steps at a time, ask how many kinds of jumps there are in n steps

The above problem seems impossible to solve, but if you use the above dynamic programming idea to think about it, you can think that the jumping method of jumping `n` steps is actually equal to the number of jumping methods for jumping `n - 1` steps, plus jumping `n - 2` The number of jumps per step. Why can you think about it this way, because jumping to the last step may be jumping up a step from the `n - 1` step, so in this case, you only need to consider how many ways to jump from the `n - 1` step. . Of course, there is another possibility, jumping up two steps from the `n - 2` 2th step. In this case, you only need to consider the number of jumping methods for the `n - 2` steps. Therefore, the jumping method of jumping `n` steps is actually equal to the sum of the jumping methods of `n-1` and `n-2` steps, namely

` `DP[n] = DP[n - 1] + DP[n - 2]``

After the transition equation is determined, we only need to determine the initial state (does it feel more like mathematical induction). A simple analysis shows that there are 1 jumping method for jumping 1 step, and 2 jumping methods for jumping 2 steps (2 jumps at a time, or 1 jump at a time and 2 jumps). which is

` `DP = 1DP = 2``

So we can build the following code logic

 ` 1 2 3 4 5 6 7 8 9 10 11 12` ` def jump (n) : if n == 1 : return 1 if n == 2 : return 2 a = 1 b = 2 for i in range( 3 , n + 1 ): tmp = a + b a = b b = tmp return b`

The above is a typical dynamic programming problem solving process. Let’s look at another question

Give k coins of denomination, the denominations are c1, c2 … ck, the number of each coin is unlimited, and then give a total amount, ask the minimum number of coins needed to make up this amount, if it is impossible to make up, the algorithm returns – 1

With the above training, we can have a little idea of ​​​​this question. First, we need to determine the state transition equation, where the state is the total amount , and the state transition is the change in the remaining amount as the amount follows the increase of coins. To know the minimum number of coins for the amount, we only need to know the minimum number of coins for the amount – `amount - c` . The minimum number of coins for the amount is the minimum number of coins for the `amount - c` plus 1. But because there are multiple coins, we also need to judge different `amount - c` , and first get the optimal solution of its preconditions.

We can get its state transition equation

` `DP[n] = min(DP[n - c1], DP[n - c2] ... DP[n - ck]) + 1``

where `DP = 0` and `DP[负数] = -1` . From this, we can construct the following code logic

 ` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 twenty one twenty two twenty three` ` def coin_problem (coins, amount) : coin_problem_table = dict() # {"amount":"number of coins"} def dp (n) : if n in coin_problem_table: return coin_problem_table[n] if n == 0 : return 0 if n < 0 : return -1 res = None for coins in coins: val = dp(n - coin) # break down into subproblems if val == -1 : continue # If there is no solution, try the next coin if res is None or res > val: res = val # optimal sub-solution if res is None : # no solution res = -1 else : res += 1 # add this new coin coin_problem_table[n] = res return res return dp(amount)`

The above problem is actually a change exchange problem of LeetCode. The above code has exceeded 93% of submissions in LeetCode, and the efficiency is still good.

We are talking about one-dimensional problems above. In fact, dynamic programming often occurs in the form of two-dimensional arrays. Let me look at an example.

A robot is located in the upper left corner of an mxn grid. The robot can only move to the right or down one grid at a time. How many ways can the robot go to the lower right corner? Seeing the problem, we can start the analysis. The path the robot takes to the lower right corner can definitely be derived from the path of the previous grid before it reaches the lower right corner. Suppose we mark the grids with coordinates, the horizontal ones are represented by i, and the vertical ones are represented by j, obviously `0 <= i <= m - 1` and `0 <= j <= n - 1` , we can also get the DP transfer equation

` `DP[i][j] = DP[i - 1][j] + DP[i][j - 1]``

In addition, we can find that all the squares in the leftmost column or the uppermost row have only one move. That is, for the leftmost column, the robot can only go down, and for the top row, the robot can only go right, so we can get the initial state

` `DP[0...m - 1] = 1DP[0...n - 1] = 1``

Get the transition equation and the initial state, then the implementation code is very simple

 ` 1 2 3 4 5 6 7 8 9 10` ` def robot_maze (m, n) : dp = [[ 0 ] * n] * m # create a two-dimensional array for i in range(m): # first line dp[i][ 0 ] = 1 for j in range(n): # first column dp[ 0 ][j] = 1 for i in range( 1 , m): for j in range( 1 , n): dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] return dp[m - 1 ][n - 1 ]`

This is also a topic of LeetCode. My implementation exceeds 91% of the time and 60% of the memory, and the efficiency is still good.

Above we introduced the idea of ​​dynamic programming and the way to solve the problem, the most important of which is the state transition and the determination of the initial state . Through these exercises, we already have some understanding of dynamic programming, and it looks like we are familiar with dynamic programming. But the fact is that the difficulty of dynamic programming is that there are too many variants, and the state transition of some problems is very abstract. When encountering these variants, it may be difficult for us to determine the state design and state transition equations, which can only be improved through continuous practice.

 ` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 twenty one twenty two twenty three twenty four 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122` ` import time def fab1 (n) : if n == 0 : return 0 if n == 1 : return 1 return fab1(n - 1 ) + fab1(n - 2 ) table = {} def fab2 (n) : if n in table: return table[n] if n == 0 : result = 0 elif n == 1 : result = 1 else : result = fab2(n - 1 ) + fab2(n - 2 ) table[n] = result return result def fab3 (n) : if n == 0 : return 0 if n == 1 : return 1 a = 0 b = 1 for i in range( 2 , n + 1 ): tmp = a + b a = b b = tmp return b def jump (n) : if n == 1 : return 1 if n == 2 : return 2 a = 1 b = 2 for i in range( 3 , n + 1 ): tmp = a + b a = b b = tmp return b def coin_problem (coins, amount) : coin_problem_table = dict() # {"amount":"number of coins"} def dp (n) : if n in coin_problem_table: return coin_problem_table[n] if n == 0 : return 0 if n < 0 : return -1 res = None for coins in coins: val = dp(n - coin) # break down into subproblems if val == -1 : continue # If there is no solution, try the next coin if res is None or res > val: res = val # optimal sub-solution if res is None : # no solution res = -1 else : res += 1 # add this new coin coin_problem_table[n] = res return res return dp(amount) def robot_maze (m, n) : dp = [[ 0 ] * n] * m # create a two-dimensional array for i in range(m): # first line dp[i][ 0 ] = 1 for j in range(n): # first column dp[ 0 ][j] = 1 for i in range( 1 , m): for j in range( 1 , n): dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] return dp[m - 1 ][n - 1 ] if __name__ == '__main__' : # x = 35 # # start = time.time() # print(fab1(x)) # print('fab1 cost: {}ms'.format((time.time() - start) * 1000)) # # start = time.time() # print(fab2(x)) # print('fab2 cost: {}ms'.format((time.time() - start) * 1000)) # # start = time.time() # print(fab3(x)) # print('fab3 cost: {}ms'.format((time.time() - start) * 1000)) # print(jump(7)) # print(coin_problem([186, 419, 83, 408], 6249)) print(robot_maze( 3 , 7 )) `