preface

Recently did some leetcode dynamic programming algorithm problem, originally I a small small vegetable chicken is not worthy to write this thing, but also brave to write their own understanding of dynamic programming and the idea of doing the problem, hope all the big guy mercy.

What is dynamic programming

To quote baidu Baike:

Dynamic programming algorithms are usually used to solve problems with certain optimal properties. In this kind of problem, there may be many possible solutions. Each solution corresponds to a value, and we want to find the solution with the optimal value.

Dynamic programming is an idea, very similar to the idea of divide and conquer

The core idea of divide-and-conquer problem is to decompose a problem into independent subproblems, solve each subproblem one by one, and then combine the answers of the subproblems to get the final solution of the problem.

The idea of dynamic programming is a little bit like divide and conquer. The difference lies in that in the idea of “divide and conquer”, each subproblem is independent, while the subproblems divided by dynamic programming are often interdependent and influence each other.

When should YOU use dynamic programming

Quote the words of the master of repairing speech

  1. Optimal substructure 2. Overlapping subproblem

Optimal substructure It means that the optimal solution of the problem contains the optimal solution of the subproblem — regardless of the previous decision, the subsequent state must be the optimal decision based on the current state (resulting from the last decision). And the overlapping subproblem, it means that in the process of recursion, there are repeated calculations.

Problem.

First of all, the leetcode simple question: 303. Region and retrieval – Array immutable

Example:

Input:

["NumArray"."sumRange"."sumRange"."sumRange"]

[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output:

[null, 1, -1, -3]



Explanation:

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);

numArray.sumRange(0, 2); // return1 (-2) + 0 + 3.

numArray.sumRange(2, 5); // returnMinus 1 (3 + -5) + 2 + -1).

numArray.sumRange(0, 5); // returnMinus 3 (-2) + 0 + 3 + (-5) + 2 + (-1).



Source: LeetCode

Link: https://leetcode-cn.com/problems/range-sum-query-immutable

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Copy the code

So what’s the definition of simple, if you think about it if we use violence to solve this problem, then it’s easy to get to the conclusion, right

var NumArray = function (nums) {

    this.nums = nums

};

NumArray.prototype.sumRange = function (i, j) {

    const arr = this.nums.slice(i, j + 1)

    return arr.reduce((a, c) => a + c)

};

Copy the code

I’ll run the results for you:

The results were dismal, with 1064ms and 47.1MB of memory. Why is that? As we can see from the example, this function of sumRange will be called many times, and we will score the cut array in it, and use reduce to sum, which is undoubtedly very expensive.

So what’s the solution? Is dynamic programming ok? You can!

Instead of calling the sumRange function multiple times, we can just call the sumRange function in the return.

So how do you optimize with dynamic programming?

The idea is to maintain a dp array inside the new function. The dp array stores the sum of all the items before nums[I] and nums passed into the array nums. So when we call sumRange we only need to return dp[j]-dp[I]

The new function code is as follows:

var NumArray = function (nums) {

    this.dp = []

    const dp = this.dp

    dp[0] = nums[0]

    for (let i = 1; i < nums.length; i++) {

        dp[i] = dp[i - 1] + nums[i]

    }

};

Copy the code

Now that we have our DP array maintained, it’s easy

   NumArray.prototype.sumRange = function (i, j) {

    const dp = this.dp;

    if (i === 0) return dp[j]

    return dp[j] - dp[i - 1]

};

Copy the code

Why do I have to add I ===0?

Because when I equals 0, we’re just taking the sum of the j terms, and there’s no I minus 1 terms. When I >1, everyone is better at math than ME, it’s easy to get dp[j] -dp [i-1]

Let’s run down the results

Perfect!

198. Raiding and pillage

Topic:

Example:

Input:,2,3,1 [1]

Output: 4

Explanation: Steal house # 1 (amount = 1), then steal house # 3 (amount = 3).

Maximum amount stolen = 1 + 3 = 4.



Source: LeetCode

Link: https://leetcode-cn.com/problems/house-robber

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Copy the code

The rule is that you can’t take contiguous items from an array. Return the maximum value under the rule

For this question, we mainly consider two cases (for the ith family) :

    1. Stealing: If we steal the i-th house, then we certainly can’t steal the I–1 house, then our maximum is the i-th house’s money plus the maximum we can steal at i-2.
    1. No stealing: If we don’t steal the i-th house, then the maximum amount of money we can steal is the maximum amount we can steal at the I-1st house.

For the example array, we draw a picture analysis: for the first company, the first company is poor, only 1 yuan, so the most money we steal from the first company is 1 yuan, the corresponding brain map and DP array are:

The second company, a middle-level leader, has 2 yuan. At this time, we have two plans:

    1. Steal the second house, at this time we can’t steal the first house, because they are adjacent, both steal will attract the police uncle, so at this time we only steal the second house. For the brain map and DP array:

The most we can steal at this point is 2

    1. Don’t steal, money I don’t steal, ah is to play! So in this case, our brain diagram and our DP array maintain the first family

Obviously, it’s better to steal the second one if we have dp[1]=2;

At this point, we can easily get math.max (dp[0],dp[1]) by stealing the maximum amount of money we can steal from the second house, which is equal to DP [1], which is 2 dollars

For the third company: senior leaders, with 3 yuan, we still have two plans:

    1. If we steal from the third house, we can’t steal from the second house, so the maximum amount we can steal is the sum of the third house’s money and the first house’s money. For the brain map and DP array:
    1. If we don’t steal the third, then the most we can steal is the most we can steal from the second:

Max (dp[1]+nums[3],dp[2]). This is the maximum we can steal from the third family.

For the fourth house, the same truth, you can manage. I’m just going to go straight to the code here

var rob = function (nums) {

    const len = nums.length

    if (len === 0) return 0;

    if (len === 1) return nums[0]

    if (len === 2) returnMath.max(... nums)

    const dp = []

    dp[0] = nums[0]

    dp[1] = Math.max(nums[0], nums[1])

    for (let i = 2; i < len; i++) {

        dp[i] = Math.max((nums[i] + dp[i - 2]), dp[i - 1])

    }

    return dp[dp.length - 1]

};

Copy the code

Last run run result:

Perfect pass!

conclusion

As I understand it, when we encounter some problems whose solution is related to each small problem, we can consider using dynamic programming to solve the problem, which can clearly clarify the logic of the problem and help us find the answer quickly!

Due to my limited technology, if there is any error, please contact me, thank you!