A brief introduction to dynamic programming

Leave a Comment / 10/06/2022 /

Original link: http://www.nosuchfield.com/2022/06/10/A-brief-look-at-Dynamic-programming/

robot_maze.png

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[1] = 1DP[2] = 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] = 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][0] = 1DP[0][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.

The complete code involved in this article is as follows

 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 ))

refer to

How to learn dynamic programming
What is Dynamic Programming? What is the meaning of dynamic programming? – Handsome answer – Knowing

This article is reprinted from: http://www.nosuchfield.com/2022/06/10/A-brief-look-at-Dynamic-programming/
This site is for inclusion only, and the copyright belongs to the original author.

Leave a Comment