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

Dynamic programming is a kind of thought, very similar to divide and conquer thought

The core idea of the divide and conquer problem is: decompose a problem into independent sub-problems, solve the sub-problems one by one, and then combine the answers to the sub-problems to obtain the final solution of the problem.

The idea of dynamic programming is somewhat similar to “divide and conquer”. The difference is that in the “divide and conquer” idea, each sub-problem is independent; while the sub-problems divided by dynamic programming are often interdependent and mutually influencing.

When to use dynamic programming

  1. Optimal substructure
  2. Overlapping subproblems

Optimal substructure It means that the optimal solution of the problem contains the optimal solution of the subproblem - regardless of the previous decision, the state after that must be the optimal decision based on the current state (resulting from the last decision) .
And overlapping subproblems, it refers to the situation of repeated calculations in the process of recursion.

do questions

First, a simple “leetcode” question: First, a simple “leetcode” question: 303. Range Sum Query - Immutable

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
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); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Why is this question defined as simple? Everyone can think about it. If this question is solved violently, then we can easily come to a conclusion.

1
2
3
4
5
6
7
8
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)
};

This result is very bleak, the execution time is 1064ms, and the memory consumption is 47.1MB. why? From the example, we can see that the “sumRange” function will be called multiple times, and we cut the score array in it and use reduce to sum, which undoubtedly consumes a lot.

So what’s the solution? Is dynamic programming possible? Can!

Idea: In order to avoid the above multiple calls, we can do the operation in one step at the time of new, and just return directly after calling the sumRange function.

So how to use dynamic programming to optimize?

My idea is to maintain a dp array inside the function when the function is new, and the dp array stores the current item nums[i] of the incoming array nums and all items before i and. In this way we only need to return dp[j]-dp[i] when calling the sumRange function

The new function code is as follows:

1
2
3
4
5
6
7
8
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]
    }
};

At this point we have maintained the dp array, and the next step is very simple

1
2
3
4
5
NumArray.prototype.sumRange = function (i, j) {
    const dp = this.dp;
    if (i === 0) return dp[j]
    return dp[j] - dp[i - 1]
};

Why add a i===0 judgment?

Because when we are at i=0, it is equivalent to taking the sum of the first j items, and there is no i-1 item at this time. When i>1, everyone learns mathematics better than me, and it is easy to draw dp[j] - dp[i - 1]

The second question: leetcode medium question: 198. House Robber

Example 1:

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

The simple understanding of this topic is that the rule is that the adjacent items of the array cannot be taken, and the maximum value under the rule is returned

For this question, we mainly consider two situations (for the i-th family):

  1. Steal: If we steal the i-th house, then we must not steal the i-1-th house, then our maximum value at this time is the money of the i-th house plus the maximum value we stole when we are i-2.

  2. Don’t steal: If we don’t steal the i-th house, then the maximum value of money we steal at this time is the maximum value we stole at the i-1th house.

For the example array

For the first house, there is only 1 gold coin, and the most money we stole from the first house is 1 gold coin. The dp array is: dp[0]=1

The second one has 2 gold coins. At this time we have two options:

  1. Steal the second house, at this time we can’t steal the first house, because they are adjacent to each other, stealing will attract the police uncle, so we only steal the second house at this time. The dp array is: dp[1]=2

    At this point the most money we can steal is 2

  2. Do not steal, then the dp array maintains the first position at this time

Obviously, it is more cost-effective to steal the second one. At this time, we dp[1]=2;

At this time, we can easily get the most money that can be stolen from the second house. Math.max(dp[0],dp[1]) is equal to dp[1], which is 2 gold coins

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

  1. Steal the third house, at this time we cannot steal the second house, so the maximum amount of money we can steal at this time is the sum of the money from the third house and the money stolen from the first house. For mindmap and dp arrays are:

  2. If we don’t steal from the third house, the most money we can steal is the most money we can steal from the second house:

At this time, we use Math.max(dp[1]+nums[3],dp[2]) to take out the maximum value of 4, which is the most money our third company can steal.
For the fourth company, the same reasoning, you can take care of it yourself. Here I will directly put the code

1
2
3
4
5
6
7
8
9
10
11
12
13
var rob = function (nums) {
    const len = nums.length
    if (len === 0) return 0;
    if (len === 1) return nums[0]
    if (len === 2) return Math.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]
};

Summarize

My understanding is: When we encounter some problems whose solution is related to each small problem that is split out, we can consider using dynamic programming to solve the problem, which can clearly clarify the logic of the problem and help us quickly solve problems. Find out!