“This is the 17th day of my participation in the August More Text Challenge.

I started writing this article in April or May, but I forgot to write 🤣 since I was busy with my graduation. You’ll have time to wrap up this article in a few days, so give it a thumbs up if you find it useful!

Note: The 21 LeetCode topics related to dynamic programming in this paper are excerpted from dynamic programming topics that are frequently investigated in CodeTop. The article is long, with a full text of about 15000 words, which can be saved as a collection

1. Overview of dynamic planning

(1) Basic concepts

Dynamic programming algorithms are usually used to solve problems with certain optimal properties. In this kind of problem, there may be many possible solutions. Every solution corresponds to a value, and we want to find the solution with the optimal value. Dynamic programming algorithm is similar to divide-and-conquer. The basic idea is to decompose the problem to be solved into several sub-problems, solve the sub-problems first, and then obtain the solution of the original problem from the solution of these sub-problems.

The subproblems derived from the decomposition of dynamic programming problems are often not independent. You need to save the answers to solved subproblems and find the saved answers when needed, so that you can avoid a lot of double counting. A table can be used to record the answers to all solved subproblems. Regardless of whether the subproblem is used later, as long as it has been computed, the result is filled into the table. This is the basic idea of dynamic programming.

Dynamic programming has two important concepts:

  • State: An intermediate result of solving a problem. It is an abstract definition of a subproblem.
  • State transition equation: recursive relation between states.

Dynamic programming solution steps:

  1. State definition: Find the subproblem abstract definition.
  2. Determine the state transition equation: find the recursive relationship between states.
  3. Initial state and boundary case: the result of the simplest subproblem and the exit condition of the program.
  4. Return value: For simple problems, the return value may be the final state; Some additional processing of the final state may be required for complex problems.

Let’s take a look at the specific application of dynamic programming by climbing stairs.

Imagine you are climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Where n is a positive integer.

Example 1:

Input:2Output:2Explanation: There are two ways to climb to the top.1. 1Order +1 阶
2. 2 阶
Copy the code

Example 2:

Input:3Output:3Explanation: There are three ways to climb to the top.1. 1Order +1Order +1 阶
2. 1Order +2 阶
3. 2Order +1 阶
Copy the code

There are two key features of this problem:

  • Ask for the number of solutions to achieve a certain goal;
  • It is not required to give the specific path corresponding to each solution.

Such problems can often be solved by dynamic programming. For this question, there are only two cases of climbing stairs each time:

  • The last step is 1 step, n minus 1 steps are in front of it, and in this case there are f(n minus 1) ways;
  • The last step is 2 steps, n minus 2 steps ahead, and in this case there are f(n minus 2) ways;

F of n is the sum of these two cases, so f of n is equal to f of n minus 1 plus f of n minus 2, and that’s the recurrence that we’re using here. Here are the four steps of dynamic programming:

  1. State definition: initializes an array of f, f[I] represents the number of methods to climb the I step;
  2. State transition equation: F (n)= F (n-1)+ F (n-2);
  3. Initial state: one step, a total of 1 climbing method; Two steps can be climbed one by one or two steps at a time. There are two ways to climb. That is, f[1] = 1, f[2] = 2;
  4. Return value: f[n], that is, how many ways to climb n steps.

The dynamic programming code is as follows:

/ * * *@param {number} n
* @return {number}* /
const climbStairs = function(n) {
    // Initialize the state array
    const f = [];
    // Initialize the known value
    f[1] = 1;
    f[2] = 2;
    // Dynamically update the result of each staircase
    for(let i = 3; i <= n; i++){ f[i] = f[i-2] + f[i-1];
    }
    // Return the target value
    return f[n];
};
Copy the code

(2) Usage scenarios

Above with the idea of dynamic planning to solve the problem of climbing stairs, of course, our purpose is not to solve this problem, but through the problem to see dynamic planning, the following to re-understand dynamic planning.

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

The idea of dynamic programming is somewhat similar to divide-and-conquer. The difference is that in divide-and-conquer, the subproblems are independent of each other: in merge sort, for example, the sorting of subarrays does not affect each other. The subproblems divided by dynamic programming are often interdependent and interactional.

So what kind of problems should we do with dynamic programming? Focus on the following key features:

  • Optimal substructure, which 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). In this case,f(n)andf(n-1),f(n-2)The relationship between the two states (state transition equations) confirms this.
  • In the recursive process of overlapping subproblem, repeated calculation occurs.
  • No aftereffect, no aftereffect has two meanings. The first meaning is that when deducing the state of the later stage, we only care about the state value of the earlier stage, not how the state is derived step by step. The second meaning is that once the status of a certain stage is determined, it is not affected by the decisions of subsequent stages. No aftereffect is a very “loose” requirement. As long as the dynamic programming problem model mentioned above is satisfied, it will basically meet no aftereffect.

Therefore, as long as the problem to be solved conforms to these three key characteristics, dynamic programming can be used to solve it.

2. The LeetCode path is faulty

(1) Different paths

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below). The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there? Example 1:

Enter: m =3, n = 7Output:28
Copy the code

Example 2:

Enter: m =3, n = 2Output:3Explanation: Starting at the top left corner, there are total3Path to the bottom right corner.1.Right -> down -> down2.Down -> down -> to the right3.Down -> right -> downCopy the code

Example 3:

Enter: m =7, n = 3Output:28
Copy the code

Example 4:

Enter: m =3, n = 3Output:6
Copy the code

Tip:

  • 1 <= m, n <= 100
  • The problem data guarantees that the answer is less than or equal to2 * 10

This problem is the same idea as the stair climbing problem, except that the stair climbing problem is a one-dimensional problem, and this problem is a two-dimensional problem. When we look at this problem, we naturally think of dynamic programming.

The path number of each grid is related to the path number on its upper and left sides, and the recursive equation can be obtained:

a[i][j] = a[i - 1][j] + a[i][j - 1]
Copy the code

Initialize a two-dimensional array of m * n. All the nodes of the array are initialized to 0. Since the top row and the leftmost column are both bounds, there is only one way to go, so the initial value is 1. And then we can solve it from the recursive equation.

/ * * *@param {number} m
 * @param {number} n
 * @return {number}* /
var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(0).map(() = > new Array(n).fill(0))

    for(let i = 0; i < m; i++){
        dp[i][0] = 1
    }
    for(let j = 0; j < n; j++){
        dp[0][j] = 1
    }

    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}return dp[m - 1][n - 1]};Copy the code

Complexity analysis:

  • Time complexity: O(Mn), where M and n are the length and width of the grid respectively. We need two layers of traversal, so the space complexity is O(Mn).
  • Space complexity: O(Mn), where M and n are the length and width of the grid respectively. We need a two-dimensional array of M * n to store all the states, so the required space complexity is O(MN).

(2) Different paths II

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Example 1:

Enter: obstacleGrid = [[0.0.0], [0.1.0], [0.0.0]] output:2Explanation: There is an obstacle in the middle of the 3x3 grid. It's going from the top left to the bottom right2Different paths:1.Right -> right -> down -> down2.Down -> down -> right -> rightCopy the code

Example 2:

Enter: obstacleGrid = [[0.1], [0.0]] output:1
Copy the code

Tip:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

This problem takes the same approach as problem 62: dynamic programming.

The difference is that obstacles appear in this problem, so the following two points need to be paid attention to when traversing:

  • When setting the initial value for the elements in the first row and column, if the value of the grid is 1, that is, there is an obstacle, it will stop directly, and there is no need to continue traversing, because it is impossible to pass in front.
  • In the calculation of the number of paths for each grid, if the grid element is directly skipped, no calculation is required.

62. What is the difference between 62 and 62?

/ * * *@param {number[][]} obstacleGrid
 * @return {number}* /
var uniquePathsWithObstacles = function(obstacleGrid) {
    if(! obstacleGrid.length || obstacleGrid[0] [0= = =1) {return 0
    }

    const m = obstacleGrid.length, n = obstacleGrid[0].length
    const dp = new Array(m).fill(0).map(() = >  new Array(n).fill(0))

    for (let i = 0; i < m && obstacleGrid[i][0] = =0; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        dp[0][j] = 1;
    }
    
    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            if(obstacleGrid[i][j] === 0){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]}}}return dp[m - 1][n - 1]};Copy the code

Complexity analysis:

  • Time complexity: O(Mn), where M and n are the length and width of the grid respectively. We need two layers of traversal, so the space complexity is O(Mn).
  • Space complexity: O(Mn), where M and n are the length and width of the grid respectively. We need a two-dimensional array of M * n to store all the states, so the required space complexity is O(MN).

(3) Minimum path sum

Given an M x N grid with non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.

Note: you can only move one step down or right at a time.

Example 1:

Input: grid = [[1.3.1], [1.5.1], [4.2.1]] output:7Explanation: Because the path1-3-1-1-1The sum of.Copy the code

Example 2:

Input: grid = [[1.2.3], [4.5.6]] output:12
Copy the code

Tip:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

For this problem, the path can only go from top to bottom, left to right. We know that the path sum of the current point is related to the path sum of the previous point, so we can use dynamic programming here.

For the elements in the first row, it can only be moved by the elements on the left, and the sum of the current elements’ paths is as follows:

grid[i][0] += grid[i - 1] [0]
Copy the code

For the elements in the first column, it can only be moved by the elements above, and the sum of the current elements’ paths is as follows:

grid[0][j] += grid[0][j - 1]
Copy the code

For elements in other positions, it can be moved from the top or from the left. Because the minimum path sum is required, we only need to select the left and top paths and minimum values. The sum relation of the current elements’ paths is as follows:

grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
Copy the code

Thus, after traversal, the value of each node is the current minimum path sum. All you need to do is return the value of the lower-right element.

/ * * *@param {number[][]} grid
 * @return {number}* /
var minPathSum = function(grid) {
    let m = grid.length, n = grid[0].length

    for(let i = 1; i < m; i++){
        grid[i][0] += grid[i - 1] [0]}for(let j = 1; j < n; j++){
        grid[0][j] += grid[0][j - 1]}for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; }}return grid[m - 1][n - 1]}Copy the code

Complexity analysis:

  • Time complexity: O(Mn), where M and n are the number of rows and columns of the grid respectively. The entire grid needs to be traversed once, calculating the value of each element of the grid.
  • Space complexity: O(1), here we operate on the basis of the original array, and the extra space required is a constant.

(4) Triangle minimum path sum

Given a triangle triangle, find the minimum sum of paths from the top down.

Each step can only move to the next node in the next row.

Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscripts of the nodes at the previous level + 1. That is, if subscript I is right on the current row, then the next subscript can be moved to I or I + 1 on the next row.

Example 1:

Input: triangle = [[2], [3.4], [6.5.7], [4.1.8.3]] output:11Explanation: As shown in the schematic diagram below:2
  3 4
 6 5 7
4 1 8 3The minimum sum of paths from top to bottom is11(i.e.,2 + 3 + 5 + 1 = 11).Copy the code

Example 2:

Enter: triangle = [[-10] Output: -10
Copy the code

Tip:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

Advanced:

  • You can just use itO(n)Additional space (nIs the total number of rows of a triangle) to solve this problem?

This problem is similar to the minimum path problem and the ladder problem, which uses dynamic programming.

Here, we don’t need to initialize an array to hold the state of each step (the minimum path value for each node), we can operate on the original array, because each node is traversed only once, after traversing, we only need to assign the state of the current node to the current node.

Here, we also need to deal with two boundary problems. For the first column, it can only be from the top element, so its state transition equation is:

triangle[i][j] += triangle[i - 1][j]
Copy the code

For the last bit of each row, it can only be down from the last bit of the previous row, so its state transition equation is:

triangle[i][j] += triangle[i - 1][j - 1]
Copy the code

For other elements, it can be moved down by its corresponding ordinal number and the element corresponding to the ordinal number minus one, so its state transition equation is:

triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
Copy the code

Finally, we just need to return the minimum value of the last row element. The extended operator, in conjunction with Math’s min method, minimizes the last line.

/ * * *@param {number[][]} triangle
 * @return {number}* /
var minimumTotal = function(triangle) {
    const n = triangle.length

    for(let i = 1; i < n; i++){
        for(let j = 0; j <= i; j++){
            if(j === 0){
                triangle[i][j] += triangle[i - 1][j]
            }else if(j === i){
                triangle[i][j] += triangle[i - 1][j - 1]}else{
                triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])}}}return Math.min(... triangle[n -1])};Copy the code

Complexity analysis:

  • Time complexity: O(n2), where n is the number of rows of the triangle.
  • Space complexity: O(1). Here we’re operating on top of the original array, so the extra space we need is constant.

3. LeetCode stock trading problem

(1) The best time to buy and sell stocks

Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make. Note: You cannot sell a stock before you buy it.

Example 1:

Input:7.1.5.3.6.4] output:5Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6-1 = 5. Notice the profit can't be7-1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Input:7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

(1) Direct traversal

We need to buy the stock once, sell it once, sell it after buy, and calculate the maximum profit.

Here we initialize a minimum value min and a maximum result value Max. Iterate through the array, and if the current array element is less than the min, update the min, always keeping it small. If the current value minus the minimum is greater than the maximum, the maximum is updated. Until all the elements of the array are iterated, and the final result is returned.

(2) Dynamic programming

For this problem, we can solve it using dynamic programming. Here we only have to make one buy and one sell. When it comes to the final trade, there are three possible states:

  • dp[0]: I haven’t bought it
  • dp[1]In the end, only one purchase, not a sale
  • dp[2]: : Finally only one sale, and sold

Since nothing is done in the first state, the record can be omitted. Then we transfer the last two states:

  • dp[1] = Math.max(dp[1], -prices[i]): the previous day was also B1 state or there is no operation, today buy a transaction into B1 state;
  • dp[2] = Math.max(dp[2], dp[1] + prices[i]): the previous day was also S1 or B1 status, today a sale becomes S1 status;

(1) Direct traversal

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let max = 0
    let min = prices[0]

    prices.forEach( item= > {
        if(item < min) min = item
        if(item - min > max) max = item - min
    })
    return max
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of the array, and we need to iterate through the array
  • Space complexity: O(1), where only constant space is needed to store min and Max

(2) Dynamic programming

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let len = prices.length;
    const dp = [0, -prices[0].0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
    }
    return dp[2];
}
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of array prices.
  • Space complexity: O(1).

(2) The best time to buy and sell stocks II

Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input:7.1.5.3.6.4] output:7Explanation: In no2Day (stock price =1) time to buy, at No3Day (stock price =5), the trade can make a profit5-1 = 4. Then, at No4Day (stock price =3) time to buy, at No5Day (stock price =6), the trade can make a profit6-3 = 3 。
Copy the code

Example 2:

Input:1.2.3.4.5] output:4Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5-1 = 4. Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input:7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Tip:

  • 1 <= prices.length <= 3 * 10
  • 0 <= prices[i] <= 10

To solve this problem, we can use dynamic programming. State description of each point: stock in hand or no stock.

1) DP [I][0] represents: no stock in hand on day I, the maximum gain so far (day I). On day I, when I don’t have any stock, there are two possibilities:

  • No shares yesterday: dp[i-1][0]
  • Prices [I] = prices[I] = prices[I] = prices[I]
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

2) DP [I][1] means: I have stocks in hand on day I, the biggest gain so far (day I). On day I, if I have stocks, there are two possibilities:

  • Yesterday there were shares: dp[i-1][1]
  • [0] – prices[I] – prices[I]
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] – prices[i])

Dp [prices.leng-1][0] = dp[prices.leng-1][0] = dp[prices.leng-1][0] = dp[prices.leng-1][0] = dp[prices.leng-1][0] = dp[prices.leng-1][0]

For the beginning:

  • Day 0 :dp[0][0] = 0
  • Day 0 æ ‡ 准 :dp[0][1] = -prices[0]
/ * * *@param {number[]} prices
 * @return {number}* /
function maxProfit(prices) {
  const len = prices.length;
  if (len < 2) {
    return 0;
  };
  const dp = new Array(len);
  dp[0] = [0, -prices[0]].for (let i = 1; i < len; i++) {
    dp[i] = new Array(2);
    dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]); // No stock
    dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]); / / there are stock
  }
  return dp[len - 1] [0];
}
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of the array. There are 2N states, and the time complexity of each state transition is O(1). Therefore, the time complexity is O(2n)=O(n).
  • Space complexity: O(n), we need to open up O(n) space to store all states in dynamic programming.

(3) The best time to buy and sell stocks III

Given an array, its ith element is the price of a given stock on day I. Design an algorithm to calculate the maximum profit you can make. You can make up to two deals. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Enter: prices = [3.3.5.0.0.3.1.4] output:6Explanation: In no4Day (stock price =0) time to buy, at No6Day (stock price =3), the trade can make a profit3-0 = 3. Then, at No7Day (stock price =1) time to buy, at No8Day (stock price =4), the trade can make a profit4-1 = 3 。
Copy the code

Example 2:

Enter: prices = [1.2.3.4.5] output:4Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5-1 = 4. Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Enter: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Example 4:

Enter: prices = [1] output:0
Copy the code

Tip:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

For this problem, we can solve it using dynamic programming. In The Best Time to Buy and Sell stocks, we can only buy and sell once. For this problem, we can buy and sell at most two times, and at the end of the transaction, there are five possible states:

  • dp[0]: I haven’t bought it
  • dp[1]In the end, I made only one purchase, not a sale
  • dp[2]: Finally only one sale, and sold
  • dp[3]: I ended up making two purchases and only one sale
  • dp[4]: I ended up buying two and selling both

Since nothing is done in the first state, the record can be omitted. Then we transfer the last four states:

  • dp[1] = Math.max(dp[1], -prices[i]): the previous day was also B1 state or there is no operation, today buy a transaction into B1 state;
  • dp[2] = Math.max(dp[2], dp[1] + prices[i]): the previous day was also S1 or B1 status, today a sale becomes S1 status;
  • dp[3] = Math.max(dp[3], dp[2] - prices[i]): the previous day was b2 or S1 state, today a purchase becomes B2 state;
  • dp[4] = Math.max(dp[4], dp[3] + prices[i]): it was s2 or B2 the day before, but now it is S2.
/ * * *@param {number[]} prices
 * @return {number}* /
function maxProfit(prices) {
    let len = prices.length;
    const dp = [0, -prices[0], -prices[0].0.0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
        dp[3] = Math.max(dp[3], dp[2] - prices[i])
        dp[4] = Math.max(dp[4], dp[3] + prices[i])
    }
    return dp[4];
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of array prices.
  • Space complexity: O(1).

(4) The best time to buy and sell stocks

Given an array of integers prices, its ith element prices[I] is the price of a given stock on day I. Design an algorithm to calculate the maximum profit you can make. You can do k transactions at most. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Enter k =2, prices = [2.4.1] output:2Explanation: In no1Day (stock price =2) time to buy, at No2Day (stock price =4), the trade can make a profit4-2 = 2 。
Copy the code

Example 2:

Enter k =2, prices = [3.2.6.5.0.3] output:7Explanation: In no2Day (stock price =2) time to buy, at No3Day (stock price =6), the trade can make a profit6-2 = 4. Then, at No5Day (stock price =0) time to buy, at No6Day (stock price =3), the trade can make a profit3-0 = 3 。
Copy the code

Tip:

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

In “The Best time to Buy and sell a stock”, we can only buy and sell once. In “The Best time to Buy and sell a stock III”, we can buy and sell twice. In this case, we can make k buys and sells. We can also use dynamic programming here.

Each time we can only make one of [1, k] trades or no trades, so there may be 2k+1 states:

  • No operation, has not bought
  • Dp [0] : In the end, only one purchase was made, but no sale was made
  • Dp [1] : In the end, only one sale was made and sold
  • Dp [2] : In the end, I bought two deals and sold only one
  • Dp [3] : In the end, I bought two deals and sold both
  • Dp [4] : In the end, I bought three deals and sold only two
  • · · · · · ·

You can enumerate all the possibilities of the day and take the maximum cash:

  • No transaction, cash stays the same
  • for[1, k]A transaction of
    • Buy, cash -= stock price of the day
    • Sell, cash += stock price of the day
/ * * *@param {number} k
 * @param {number[]} prices
 * @return {number}* /
var maxProfit = function(k, prices) {
    const dp = new Int16Array(k * 2).fill(-prices[0])
    
    for (let i = 0; i < prices.length; i++) {
        for (let j = 0; j < dp.length; j++) 
            {
                dp[j] = Math.max(dp[j], (dp[j - 1] | |0) + (j & 1 ? prices[i] : -prices[i]))
            }
    }
    return Math.max(0. dp) };Copy the code

Complexity analysis:

  • Time complexity: O(n * min(n, k)), where n is the length of array prices, that is, the time required for dynamic programming using double loops.
  • Space complexity: O(min(n,k)).

4. LeetCode robbery problem

(1) Robbery

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

Example 1:

Input:1.2.3.1] output:4Explanation: Stealing1House no. (Amount =1) and steal3House no. (Amount =3). Maximum amount stolen =1 + 3 = 4 。
Copy the code

Example 2:

Input:2.7.9.3.1] output:12Explanation: Stealing1House no. (Amount =2), and steal3House no. (Amount =9) and steal5House no. (Amount =1). Maximum amount stolen =2 + 9 + 1 = 12 。
Copy the code

Tip:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

For this problem, we can use dynamic programming. Let’s start with the two simplest cases, if there’s only one house, that house is the highest amount, if there’s two houses, you can’t steal at the same time, you can only steal the one with the highest amount, if there’s more than two rooms, we have to discuss.

  • If you steal the NTH room, then you can’t steal the n-1 room, so the total amount is the sum of the highest amount that can be stolen from the first N-2 rooms;
  • If the k room is not stolen, then the total amount of money can be stolen is the highest total amount of the previous K-1 room.

In both cases, we just take the larger value of the total amount.

We can use DP [I] to represent the maximum amount of money that can be stolen from the previous I house, then we have the following state transition equation:

Dp [I] = Max (dp [I -2[I] + nums [I], dp -1])
Copy the code

Boundary conditions are as follows:

  • Dp [0] = nums[0] : there is only one house, then steal the house
  • Dp [1] = Max (nums[0], nums[1]) : there are only two houses, choose the house with the higher amount to steal

The final answer is dp[n−1], where n is the length of the array.

/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function(nums) {
    const len = nums.length
    if(! len){return 0
    }

    const dp = new Array(len + 1)
    dp[0] = 0
    dp[1] = nums[0]

    for(let i = 2; i <= len; i++){
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
    }
    return dp[len];
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the array length. You only need to iterate through the array once.
  • Space complexity: O(1). Use arrays to store only the highest sum of the first two houses, not the results of the entire array, so the space complexity is O(1).

(2) Robbery II

You are a professional thief, planning to rob the houses along the street, each with a certain amount of cash hidden inside. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal without setting off the alarm. Example 1:

Enter: nums = [2.3.2] output:3Explanation: You can't steal first1House no. (Amount =2) and steal3House no. (Amount =2), because they are adjacent.Copy the code

Example 2:

Enter: nums = [1.2.3.1] output:4Explanation: You can steal first1House no. (Amount =1) and steal3House no. (Amount =3). Maximum amount stolen =1 + 3 = 4 。
Copy the code

Example 3:

Enter: nums = [0] output:0
Copy the code

Tip:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

In fact, this kind of problem can use dynamic programming to answer, this topic and robbery similar, but is more than two cases:

  • Don’t steal the first house
  • Don’t steal the last one

So you can sort things out, and when you don’t steal the first house, you exclude the first house, and you do the calculation for the other houses, and when you don’t steal the last house, you exclude the last house, and you do the calculation for the other houses.

The maximum value of the current node is the maximum value of the sum of the current node and the second node before it and the value of the last node.

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

Code implementation:

/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function(nums) {
    const len = nums.length
    let res1 = 0, res2 = 0
    if(len === 0) return 0
    if(len === 1) return nums[0]

    const dp = new Array(len)
    
    // Don't steal the first one
    dp[0] = 0
    dp[1] = nums[1]
    for(let i = 2; i <= len - 1; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res1 = dp[len - 1]

    // Don't steal the last one
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i <= len - 2; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res2 = dp[len - 2]
    return Math.max(res1, res2)
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of the array and we need to traverse the array twice;
  • Space complexity: O(n), where n is the length of the array, we need to initialize an array of length N to hold the state of the current node.

(3) Robbery III

After robbing a street and a circle of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the Root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that “all the houses in this place are arranged like a binary tree.” If two directly connected houses are robbed on the same night, the house will automatically alarm the police.

Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.

Example 1:

Input:3.2.3.null.3.null.1]
     3
    / \
   2   3
    \   \ 
     3   1Output:7Explanation: The maximum amount a thief can steal in one night =3 + 3 + 1 = 7.
Copy the code

Example 2:

Input:3.4.5.1.3.null.1]
     3
    / \
   4   5
  / \   \ 
 1   3   1Output:9Explanation: The maximum amount a thief can steal in one night =4 + 5 = 9.
Copy the code

For this problem, we can use dynamic programming.

For binary trees, where each node has two states, selected or unselected, we can traverse the tree using depth-first traversal:

  • When a node is selected, its left and right children cannot be selected, so the maximum value is node.val + left[1] + right[1];
  • Math.max(left[0], left[1]) + math.max (right[0], right[1]); math.max (right[0], right[1]);

Return the maximum value of the left and right subtrees.

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var rob = function(root) {
    const dfs = (node) = > {
        if (node === null) {
            return [0.0];
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
      
        const select = node.val + left[1] + right[1];
        const notSelect = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [select, notSelect];
    }
    const res = dfs(root)
    return Math.max(res[0], res[1])};Copy the code

Complexity analysis:

  • Time complexity: O(n), a post-order traversal of the binary tree, so the time complexity is O(n);
  • Space complexity: O(n), the cost of using recursive stack space is O(n).

5. LeetCode palindrome string problem

(1) the subroutine string

Given a string, your task is to calculate how many substrings are in the string. Substrings with different starting or ending positions are treated as different substrings, even if they are composed of the same characters.

Example 1:

Input:"abc"Output:3Explanation: three anagram substrings:"a"."b"."c"
Copy the code

Example 2:

Input:"aaa"Output:6Explanation:6A string of subscripts:"a"."a"."a"."aa"."aa"."aaa"
Copy the code

Tip: Enter a string of no more than 1000 characters.

The most straightforward way to solve this problem is to use a cycle of violence, going through every possibility, as follows:

  • First of all, we can see from the problem that each element is itself a substring, so we add the length of the string
  • Defines a function to check if a string is a palindrome
  • The string is traversed in two layers, intercepting all substrings of the string, and determining whether it is a palindrome string

Complexity analysis:

  • The time complexity is O(n2), requiring two layers of traversal.
  • Space complexity is O(1).
/ * * *@param {string} s
 * @return {number}* /
var countSubstrings = function(s) {
    let count = s.length
    let len = s.length
    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            let temp = s.substr(i, j-i+1)
            if(isSub(temp)){
                count++
            }
        }
    }
    return count
};
const isSub = str= > {
        let a = 0
        let b = str.length - 1
        while(a <= b){
            if(str[a] ! == str[b]){return false
            }
            a++
            b--
        }
        return true
    }
Copy the code

(2) the longest loop substring

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.

Example 1:

Input:"babad"Output:"bab"Note:"aba"It's also a valid answer.Copy the code

Example 2:

Input:"cbbd"Output:"bb"
Copy the code

There are two ways to answer this question:

(1) Method 1: Center extension method

The idea of the center extension method is to enumerate the center of possible palindromes and spread out from this center to both sides as far as possible to obtain a palindrome string. The specific implementation steps are as follows:

  • Select the center of symmetry (the middle of two characters in an odd-length string, and the middle character in an even-length string)
  • By comparing the extended length of the two combinations of larger substring length
  • Compare the previous length to determine whether to update the starting position
  • After traversing, the longest loop substring is intercepted based on the starting position

Code implementation:

/ * * *@param {string} s
 * @return {string}* /
var longestPalindrome = function(s) {
    if(s == null || s.length <1) {return ' '
    }
    let start = 0
    let end = 0
    // Define the central extension method
    const fn = (s,left,right) = > {
        while(left >=0 && right< s.length && s[left] === s[right]){
            left--
            right++
        }
        return right - left -1
    }
    // Iterate over the string
    for(let i = 0; i<s.length; i++){
        const len1 = fn(s, i, i)
        const len2 = fn(s, i, i+1)
        const len = Math.max(len1, len2)
        // Check whether the starting position is updated
        if(len > end - start){
            start = i- Math.floor((len-1) /2)
            end = i+ Math.floor(len/2)}}return s.substring(start, end+1)};Copy the code

Complexity analysis:

  • Time complexity: O(n2), the time complexity of enumerating “central location” is O(n), and the time complexity of diffusing from “central location” to obtain “loop substring” is O(n), so the time complexity is O(n2).
  • Space complexity: O(1), where only two constant temporary variables start and end are used, so the space complexity is O(1).

(2) Method two: dynamic programming

The core idea of solving this kind of problem is two word extension, specifically

  • If a string is a palindrome string, it must still be a palindrome string by adding the same character to the left and right
  • If you add any characters at either end of a string that is not a palindrome string, or if you add different characters to the left and right of a palindrome string, the result is definitely not a palindrome string

In fact, the above analysis has established correlations between big problems and small problems because we can model dynamic programming. Dp [I][j] can be used to indicate whether palindromes from I to j (including I and j) in S can be formed. The state transition equation only converts the above description into code:

if (s[i] === s[j] && dp[i + 1][j - 1]) {
  dp[i][j] = true;
}
Copy the code

Among them:

  • S [I] === S [j] : indicates that the current center can continue to expand, and possibly expand the length of the palindrome string
  • Dp [I +1][J-1] : true, indicating that the substring s[I +1][J-1] of S [I,j] is also a palindrome string, where I is traversed from the maximum value and j is traversed from the minimum value

To summarize, the specific implementation steps using dynamic programming are as follows:

  • Determine the dp [I] [j] is a palindrome, only need to dp [I + 1] [1] [I] is a palindrome and s = = = s [j].
  • The loopback of length 0 or 1 needs special treatment, that is, J-i < 2;
  • Since knowing dp[I] requires knowing dp[I +1], I needs to be traversed from large to small
  • Because knowing dp[j] requires knowing DP [J-1] first, j needs to be traversed from small to large

Code implementation:

 / * * *@param {string} s
 * @return {string}* /
// Extension center
var longestPalindrome = function(s) {
   let res = ' ';
    let n = s.length;
    let dp = Array.from(new Array(n), () = > new Array().fill(0));
    
    for(let i = n-1; i >=0; i--) {
        for(let j = i; j < n; j++) {
            dp[i][j] = s[i] === s[j] && ( j - i < 2 || dp[i+1][j-1])
            if(dp[i][j] && j - i + 1 > res.length) {
                res = s.substr(i,j - i + 1); }}}return res;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n2), where n is the length of the string. The total number of states in dynamic programming is O(n2), and for each state, the time required for transition is O(1).
  • Space complexity: O(n2), that is, the space required to store the dynamically planned state.

(3) Longest sequence of rhymes

Given a string s, find the longest sequence of subroutines and return the length of the sequence. We can assume that the maximum length of s is 1000.

Example 1:

Input:"bbbab"Output:4The longest possible sequence of subrons is zero"bbbb".Copy the code

Example 2:

Input:"cbbd"Output:2The longest possible sequence of subrons is zero"bb".Copy the code

Tip:

  • 1 <= s.length <= 1000
  • sContains only lowercase letters

For this kind of substring problem, we can consider whether dynamic programming can be used to solve it.

Here we try to use dynamic programming to solve the problem, initialize a two-dimensional dp array to store the length of the substring, dp[I][j] represents the length of the longest palindrome sequence from the i-th character to the j-th character in s.

The most important thing is to find the state transition equation:

  • If the i-th and JTH characters of string s are the same:f[i][j] = f[i + 1][j - 1] + 2
  • If the i-th and JTH characters of string s are not the same:f[i][j] = max(f[i + 1][j], f[i][j - 1])

Note the order in which I is traversed from the last character and j is traversed backwards from I +1 to ensure that each subproblem has been evaluated. Finally, simply return dp[0][len-1].

/ * * *@param {string} s
 * @return {number}* /
var longestPalindromeSubseq = function(s) {
    let len = s.length;
    
    let dp = new Array(len)
    for (let i = 0; i < len; i++) {
        dp[i] = new Array(len).fill(0);
    }
    
    for (let i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i+1; j < len; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])}}}return dp[0][len-1];
};
Copy the code

Complexity analysis:

  • Time complexity: O(n2), where n is the length of the string, we need a two-layer traversal;
  • Space complexity: O(n2), where n is the length of the string, we need to initialize a two-dimensional array.

6. LeetCode subsequence problem

(1) Maximum suborder sum

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example:

Input: [...2.1, -3.4, -1.2.1, -5.4] output:6Continuous subarrays [4, -1.2.1] and maximum, for6.Copy the code

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Dynamic programming solution: There are usually three ways to traverse a substring or subsequence

  • All subsequences starting with a node, such as [a], [a, b], [a, b, c]… Iterate over [b] [b, c] from the subsequence starting with b.
  • According to the length of the subsequence as the benchmark, such as traversing the subsequence of length 1, traversing the length 2 and so on.
  • Based on the end node of a subsequence, all subsequences ending at a node are first traversed, because each node may be the end node of a subsequence, so the whole sequence is traversed, for example, all subsequences ending at b: [A, b] [b], and all subsequences ending at C: A, B, C [b, C] [C].

Among them, the first method usually uses the method of violence to solve, the second method has been used in the fifth question above, the emphasis is on the third method: Since recursive relations can be generated, such traversal method is often adopted when dynamic programming is adopted, such as backpack problem and maximum common substring. The dynamic programming solution here is also based on the idea of traversing all subsequences ending with a node.

Code implementation:

var maxSubArray = function(nums) {
    let sum = 0, res = nums[0]
    for(let num of nums){
        sum > 0 ? sum += num : sum = num
        res = Math.max(sum, res)
    }
    return res
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of the NUMS array, and you only need to traverse the array once to get the answer.
  • Space complexity: O(1), only need constant space to store several variables.

(2) the longest increasing subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Enter: nums = [10.9.2.5.3.7.101.18] output:4Explanation: The longest increasing subsequence is [2.3.7.101], so the length is4 。
Copy the code

Example 2:

Enter: nums = [0.1.0.3.2.3] output:4
Copy the code

Example 3:

Enter: nums = [7.7.7.7.7.7.7] output:1
Copy the code

Tip:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Advanced:

  • Can you design a solution with O(n2) time?
  • Can you reduce the time complexity of the algorithm down to order n log n?

Dynamic programming is the easiest thing to think of when dealing with subsequences. We initialize an array dp to hold the optimal solution of each subproblem. Dp [I] represents the longest continuous subsequence of the elements in the first n of the array. Finally, we return the longest sequence of all subsequences.

/ * * *@param {number[]} nums
 * @return {number}* /
var lengthOfLIS = function(nums) {
    const n = nums.length
    if(! n){return 0
    }

    let dp = new Array(n).fill(1)
    for(let i = 1; i < n; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1)}}}return Math.max(... dp) };Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of array NUMs. The number of states in dynamic programming is N, and it takes O(n) time to traverse all states of DP [0… I −1] when calculating state DP [I], so the total time complexity is O(n).
  • Space complexity: O(n), additional DP array of length N is required.

(3) The subarray with the largest product

Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

Example 1:

Input:2.3, -2.4] output:6Explanation: Subarray [2.3] has maximum product6.Copy the code

Example 2:

Input: [...2.0, -1] output:0Explanation: The result cannot be2Because [...2, -1] is not a subarray.Copy the code

To solve this problem, we can use dynamic programming.

We just need to update the maximum value as we iterate through the array. In this process, we need to maintain two values:

  • Max, the current maximum value, compares the current value with the product of the current value and the previous maximum value, saving the maximum value
  • Min, the current minimum value, compares the current value with the product of the current value and the previous minimum value, saving the minimum value

We’re taking the maximum here, so why save the minimum? This is because there can be negative numbers in the array, and when the current value is negative, multiplying the previous value causes the maximum and minimum to be swapped, so we need to maintain a maximum and a minimum. Then keep using the current maximum value as the result, and finally return the result.

/ * * *@param {number[]} nums
 * @return {number}* /
var maxProduct = function(nums) {
    let res = -Infinity, max = 1, min = 1;

    for(let i = 0; i < nums.length; i++){
        if(nums[i] < 0) {let temp = max
            max = min
            min = temp
        }
        max = Math.max(nums[i], nums[i] * max)
        min = Math.min(nums[i], nums[i] * min)

        res = Math.max(res, max)
    }
    return res
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), we need to walk through the array, so time complexity is O(n);
  • Space complexity: O(1), where the extra space we need is constant, so space complexity is O(1).

(4) The longest repeating subarray

Given two integer arrays A and B, return the length of the longest common subarray of the two arrays.

Example:

Input:A: [1.2.3.2.1]
B: [3.2.1.4.7] output:3Explanation: The longest common subarray is [3.2.1].Copy the code

Tip:

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

We can solve this problem by using dynamic programming. Dynamic programming is to keep the previous state related to the next state and continuous. The subarray here is like a substring, it’s continuous.

Here we initialize A dp array to hold the current maximum contiguous value. Dp [I][j] represents the length of the longest common subarray consisting of the first I elements of array A and the first J elements of array B.

When iterating through a number group:

  • If the current two elements are equal, i.e. A[I] === B[j], then the current element can form A common subarray, so let the length of the longest common subarray of the previous element add one, then the state transition equation is: dp[I][j] = dp[i-1][j-1] + 1;
  • If the current values of the two elements are not equal, then the dp value is saved to 0 (initialized to 0).

During traversal, the maximum value of the longest common subsequence is constantly updated.

/ * * *@param {number[]} A
 * @param {number[]} B
 * @return {number}* /
var findLength = function(A, B) {
    const m = A.length, n = B.length;

    let dp = new Array(m + 1)
    for (let i = 0; i <= m; i++) { 
        dp[i] = new Array(n + 1).fill(0);
    }

    let res = 0

    for(let i = 1; i <= m; i++){
        for(let j = 1; j <= n; j++){
            if(A[i - 1] === B[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    return res
};
Copy the code

Complexity analysis:

  • Time complexity: O(mn), where M and n are the lengths of two arrays A and B respectively. Here we need two layers to traverse the two arrays.
  • Space complexity: O(mn), where m and n are the lengths of two arrays A and B respectively, we need to initialize A TWO-DIMENSIONAL array DP to store the length of the current longest common subarray.

7. Other problems with LeetCode

(1) Rain water

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.

Example 1:

Enter: height = [0.1.0.2.1.0.1.3.2.1.2.1] output:6Explanation: The above is made up of arrays [0.1.0.2.1.0.1.3.2.1.2.1] represents the height diagram, in this case, can be connected61 unit of rain (blue indicates rain).Copy the code

Example 2:

Enter: height = [4.2.0.3.2.5] output:9
Copy the code

Tip:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

The depth of rain on each pillar depends on the length of the shorter of the tallest on either side of it.

  • If the length of the shorter column is greater than the length of the current column, the depth of the rain is the shorter column minus the length of the current column;
  • If the length of the shorter column is less than or equal to the current column, then the depth of the rain is 0.

For subscript I, the maximum height that water can reach after rain is equal to the minimum of the maximum height on both sides of subscript I, and the amount of rain water that can reach subscript I is equal to the maximum height that water can reach at subscript I minus height[I].

The most straightforward approach is to scan left and right for each element in the height array and record the maximum height on the left and right, then calculate the amount of rain water that can be reached at each subscript position. Using the method of dynamic programming, the maximum height on both sides of each position can be preprocessed in O(n) time.

/ * * *@param {number[]} height
 * @return {number}* /
var trap = function(height) {
    let len = height.length, sum = 0
    for(let i = 0; i < len - 1; i++){
        // Calculate the maximum value to the left of the current column
        let left = 0
        for(let j = i - 1; j >= 0; j--){
            left = Math.max(height[j], left)
        }
        // Calculate the maximum value on the right side of the current column
        let right = 0
        for(let j = i + 1; j < len; j++){
            right = Math.max(height[j],right)
        }
        // Calculate the amount of rain water that the current column can receive
        if(min > height[i]){
            sum += Math.min(left, right) - height[i]
        }
    }
    return sum
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of array height. We need to iterate over the height array twice;
  • Space complexity: O(1).

(2) Climb the stairs

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input:2Output:2Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2 阶
Copy the code

Example 2:

Input:3Output:3Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3.  2Order +1 阶
Copy the code

When we look at this problem, what we should think about is dynamic programming, breaking up a big problem into subproblems. First up:

  • The first step: 1 method
  • Second step: 2 ways
  • Step N: Climb one step from the n-1 step or two steps from the n-2 step

So we can get the recursive formula: f(n) = f(n−1) + f(n−2) and then we can do the calculation recursively.

The ordinary recursion above is obvious, and there is a lot of double computation, so we can save the result of each calculation and use it directly the next time.

Ordinary recursion:

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i ++){
        dp[i] = dp[i - 1] + dp[i - 2]}return dp[n]
};
Copy the code

Memory recursion:

/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function(n) {
    let a = 1, b = 1, res = 1;
    for (let i = 1; i < n; i++) {
        a = b
        b = res
        res = a + b
    }
    return res
};
Copy the code

Ordinary recursive complexity analysis:

  • Time complexity: O(n2), the depth of the recursion tree is N, so the time complexity is O(n2);
  • Space complexity: O(n), where we need to initialize an array to hold the number of methods for each step, there are n numbers, so the space complexity is O(n);

Recursive complexity analysis of memory:

  • Time complexity: O(n), n times of cyclic execution, so time complexity is O(n);
  • Space complexity: O(1), where only constant variables are used as auxiliary space, so the space complexity is O(1);

(3) Maximum square

In a two-dimensional matrix of ‘0’ and ‘1’, find the largest square containing only ‘1’ and return its area.

Example 1:

Input: matrix = [["1"."0"."1"."0"."0"], ["1"."0"."1"."1"."1"], ["1"."1"."1"."1"."1"], ["1"."0"."0"."1"."0"]] output:4
Copy the code

Example 2:

Input: matrix = [["0"."1"], ["1"."0"]] output:1
Copy the code

Example 3:

Input: matrix = [["0"]] output:0
Copy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

For this problem, we can use dynamic programming to solve it. Here we need to initialize a dp array, dp[I][I] represents the maximum side length of the square with (I, j) as the bottom right corner and only 1. All we need to do is walk through this two-dimensional matrix, the value of each dp of the computer, pick the maximum, the maximum side length of the square, and finally return the area of the square.

Calculating each value of dp has the following rules:

  • If the current value is 0, then the point does not exist in the square, directly assign dp[I][j] to 0;
  • If the current value is 1, the value of dp[I][j] is determined by the minimum of its upper, left and upper left values, so its state transition equation is:
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
Copy the code

In addition, we also need to consider the leftmost column and the uppermost row of the two-dimensional matrix. If the value is 1, we directly assign dp[I][j] to 1.

Code implementation:

/ * * *@param {character[][]} matrix
 * @return {number}* /
var maximalSquare = function(matrix) {
    const m = matrix.length, n = matrix[0].length
    let res = 0
    if(! matrix || m ===0 || n === 0) {return 0
    }

    let dp = new Array(m)
    for(let i = 0; i < m; i++){
        dp[i] = new Array(n).fill(0)}for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(matrix[i][j] === '1') {if(i === 0 || j === 0){
                    dp[i][j] = 1
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                }
                res = Math.max(dp[i][j], res)
            }
        }
    }
    return res * res
};
Copy the code

Complexity analysis:

  • Time complexity: O(Mn), where M and n are the number of rows and columns of a two-dimensional matrix. We need to iterate through every element of the two-dimensional matrix to compute dp.
  • Space complexity: O(Mn), where M and n are the number of rows and columns of a two-dimensional matrix. We create an array dp of the same size as the original matrix to hold the maximum side length of the current square.

Related articles recommended:

  • 3.5 w word | 47 LeetCode topic show you those routines binary tree (on)

  • 3.5 w word | 47 LeetCode topic show you those routines binary tree (below)

  • 2 w word | 28 LeetCode topic show you the list of those routines