This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

What is dynamic programming?

“Dynamic Programming (DP) is a branch of operations research, which is the process of solving the optimization of decision processes. — From Baidu Baike

What problem should be solved by dynamic programming?

We usually use dynamic programming to solve optimal problems. Such as maximum sequence combination, longest/short path, best time, etc., we can consider whether to use dynamic programming to solve the optimal problem.

How to solve the problem with dynamic programming?

  • Determine the recursion state
  • Determine the state transition equation
  • Determining boundary conditions
  • algorithm

What about chestnuts?

746 use the minimum cost to climb stairs

And we can see from the minimum cost, that this problem can be solved by dynamic programming. Let’s draw a picture first and then solve the problem step by step:

  • Determine the recursion state

f(x) = y;

Y is what we took, the amount of effort it took to get to step I.

So x is what causes y to change. What are the factors? In this problem, only the number of steps is the dependent variable, so let’s define x as the number of steps.

  • Determine the state transition equation

There are problems and diagrams, and we can see, how do I get to dp[I]? Either go up from the first to last step and cost DP [i-1] + Costs [I-1], or go up from the second to last step and cost DP [I-2]+costs[I-2]. And they want to know the minimum cost, so I’m just going to take the smaller of both.

Therefore, we can define the state transition equation as:

dp[i] = min(dp[i-1] + costs[i-1], dp[i-2] + costs[i-2])
Copy the code
  • Defining boundary conditions

We know from the state transition equation, if we want to know the cost of the ith step, we know the cost of the last step and the one before it, then the boundary conditions are the first and second steps. Climbing the first and second steps costs nothing. (Both the first and second steps can be climbed at one time, so there is no cost here. Costs [I] are required only when we climb up steps that cost us, such as the first or second step)

    dp[0] = 0;
    dp[1] = 0;
Copy the code
  • algorithm
    var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = []
    dp[0] = 0;
    dp[1] = 0;
    for (let i = 2; i <= n; i++) {
        dp[i] = Math.min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2))}return dp[n]
};
Copy the code

OK, let’s do some simple dynamic programming problems

Yang hui triangle

In this case, f of x is equal to y. It doesn’t seem right to define y as row I, so y is an array, and we want it to be an exact value. So let’s define y as the ith row and the JTH bit, and then we’re going to evaluate all of the ith row. Thus, the state transition equation can be obtained as

    // dp[I][j] // dp[I][j
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
Copy the code

The code is as follows:

var getRow = function(rowIndex) {
    // Array length
    const n = rowIndex + 1;
    // Initializes the two-dimensional array with a value of 1, so that the boundary condition of Yang's triangle is omitted
    const dp = new Array(n).fill(1).map(() = > new Array(n).fill(1))
    
    for(let i = 1; i < n; i++) {
        for (let j = 1; j < i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        }
    }

    return dp[n - 1]};Copy the code

Al shabaab

The title looks exciting… Learn algorithm re – employment can also profit maximization…

We want to figure out the maximum amount of money that we can get for stealing house I, because they tell us that we can’t steal house I in succession, so the maximum amount of money that can be stolen from house I is the maximum amount of money that can be stolen from house I-1 and the maximum amount of money that can be stolen from house I-2 plus the sum of house I.

So we directly define the state transition equation dp[I] = Max (dp[i-1], dp[i-2] + NUMs [I])

According to the state transition equation, dp[I] is only related to dp[i-1] and dp[i-2], so we can only define an array of length 3, and then replace the values in turn to save space. This optimization method is called scrolling arrays.

The code is as follows:

var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0]
    const dp = new Array(3)
    
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    
    for (let i = 2; i < n; i++) {
        const idx = i % 2;
        const idx_pre = (i - 1) % 2;
        const idx_pre_pre = (i - 2) % 2
        dp[idx] = Math.max(dp[idx_pre], dp[idx_pre_pre]+nums[i])
    }
    return dp[(n - 1) % 2]};Copy the code

To paint the house

Paint the house as soon as you finish stealing it. Probably out of a labor camp…

I’ll leave that to you to think about. Leave a message with some random state transition equation, okay? There is still room for optimization on the topic above, and I hope you can leave a message to discuss ~ when I learn two more days, and then a dynamic programming 2.0, 3.0 difficulty of the topic analysis.

😀😀😀 welcome to discuss, please remember to click 👍 😀. The code of this article has been put on Github, and there are other topics of dynamic programming, which have not been written in the article, but are written in Git. There are the previous algorithm code, the subsequent code will also be updated, welcome you to comment.