Dynamic programming

Introduction – Climb the stairs

Before we dive into dynamic programming, let’s look at a classic problem

1. Climb the stairs

Suppose you are climbing the stairs. It takes n steps to get to the top.

You can climb 1 or 2 steps at a time. How many different ways can you climb to the top of a building?

2. Problem analysis

Let’s say that the total number of steps is 10, and we’re not going to worry about steps 0 to 8, and we’re not going to worry about steps 0 to 9, but in order to get to step 10, we have to make two choices in the last step.

1. Take the ninth step and climb the second step

Now a new question arises, if we know that there are x ways to go from 0 to 9 steps, and y ways to go from 0 to 8 steps, how many ways can we go to 10 steps? And the answer is x plus y

So how many ways are there to get to the ninth step? And we can continue to do the analysis along these lines

3. Problem generalization

Let’s say we’re on the ith step, and given what we know, we can only take one or two steps at a time, so there are two ways to get to the ith step

1. Climb 1 step from the first to the second. 2

Let’s say we know that there are f(I -1) ways to get to the I -1 step, and f(I -2) ways to get to the I -2 step

If there are f(i-1) ways to get to the i-1 step, and f(i-2) ways to get to the i-2 step,

So there are f(I) ways to get to order I, which is equal to the number of ways to get to order I minus 1, plus the number of ways to get to order I minus 2, f(I minus 2).

So f(I) = f(I -1)+f(I -2)

The above process is to break down a big problem into small problems one by one, and then analyze them layer by layer to get the final result

In fact, the problem of climbing stairs is a problem of solving the Fibonacci sequence

3. General solution of Fibonacci sequence

We solve this problem by recursively going from the NTH level down to the final result

func fib(n int) int {
    if n < 0 {
        return 0
    } else if n <= 1 {
        return 1
    } 
    
    return fib(n-1) + fib(n-2)
}

Let’s take order 5 as an example

<img src=”https://test-kefu-zs.oss-cn-shenzhen.aliyuncs.com/zjalpha/mobilecheckqualitytool/39fc0af2-2a42-dc6e-64bf-ab936fad74 34.png” style=”zoom:50%;” />

As can be seen from the figure above, the recursive solution has the following defects:

  1. The colored part has double counting, the larger the value of n, the more double counting
  2. The number of recursive layers deepens as the value of n increases, triggering the maximum function nesting layer of the system
  3. The time complexity of the algorithm is O(2^n).

Are there other ways to solve this problem? Is it possible to solve this problem with the dynamic programming mentioned at the beginning? Let’s take a look at dynamic programming, see if it can solve the stair climbing problem, and explore its relationship to recursion

Text – dynamic programming

1. The concept

Dynamic Programming (DP)Operations research is a branch of operations research
Multistage decision makingA type of process optimization
Mathematical methods. Transform a multi-stage problem into a series of interrelated single-stage problems, and then solve them.

2. Problems that DP can solve

A problem suitable for dynamic programming must satisfy the following conditions:

Optimal substructure: The substrategy of an optimal strategy is always optimal.

No after-effect: the historical status of the problem does not affect the future development; It can only affect the future through the present state; The current state of affairs is a summary of past history

3. The idea of solving problems with DP

  1. State definition: Describes the state information at time I

    1. Find the state transition equation: Find the recursive relation for the state

4. How to use DP to climb stairs (Fibonacci series problem)

1. State definition: the total way of fib[n] to reach the NTH step

2. State transition equation (recursion) : There are two ways to reach the NTH order: from order n-1, or from order n-2, so

​ fib[n] = fib[n-1] + fib[n-2]

The following code

Func fib(n int) int {if n < 0 {return 0} Dp [] var dp = make([]int, n+1) dp[0] = 1 dp[1] = 1 for I :=2; i<=n; i++ { dp[i] = dp[i-1]+dp[i-2] } return dp[n] }

Algorithm time complexity: O(n)

Space complexity: O(n), can be optimized to O(1)

So if you look at this, do you see the relationship between recursion and dynamic programming

Both recursion and dynamic programming are about breaking a large problem into smaller problems. Dynamic programming = recursion + memorization (storing solutions to subproblems)

Difference: Dynamic programming is bottom-up, while recursion is bottom-up

Now, let me give you another example

chestnuts

Minimal paths and problems

Description: Given an M x N grid with non-negative integers, find a path from the top left to the bottom right so that the sum of the numbers on the path is minimized.

Directions: Only one step down or right at a time.

Analysis of the

1. Since the problem is to find the minimum path sum, we define the state dp[I][j] as the minimum path sum in row I [j]

2. Since the direction of the path can only be down or right, the possible result of dp[I][j] is coming from the top dp[i-1][j] or the left dp[I][j-1] of the current position, so the minimum path of the current position is the minimum value of the top or left path plus the value of the current position, so the state transition equation can be obtained

​ dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

Based on the above analysis, the following code is obtained

func minPathSum(grid [][]int) int { m := len(grid) n := len(grid[0]) var minPath = make([][]int, m+1) for i:=0; i<m; i++ { minPath[i] = make([]int, n+1) } var min int for i:=0; i<m; i++ { for j:=0; j<n; If I == 0 &&j == 0 {min =0} else {if I == 0 {j++ {// j++ {// j++ {// j++ {j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++ {// j++; } else j= =0 {// j=0} else j= =0 {// j=0} MinPath [I -1][j]} else minPath[I -1][j] > minPath[I][j-1]} else minPath[I -1][j] > minPath[I][j-1] { MinPath [I][j]} else {minPath[I][j]} minPath[I][j] = min + grid[I][j]} return minPath[m-1][n-1] }

conclusion

Dynamic programming is widely used in daily life, including engineering technology, economy, industrial production, military and automation control and other fields, and has achieved remarkable effects in backpack problem, production and operation problem, fund management problem, resource allocation problem, shortest path problem and complex system reliability problem.

This article aims to help you to have a basic understanding of dynamic programming and broaden your thinking on how to deal with problems. Of course, if you are interested in dynamic programming, you can continue to look for related topics and improve your understanding of it.