Dynamic programming

Dynamic programming (DP) is a branch of operations research. It is a mathematical method to optimize the decision-making process. It is a method to solve complex problems by breaking down original problems into relatively simple sub-problems.

A list,

The idea of dynamic programming is to simplify complex problems into simple problems by stages.

Dynamic programming is often applied to problems with overlapping subproblems and optimal substructures, and the time consumed by dynamic programming is often much less than that of the naive solution.

The basic idea behind dynamic programming is very simple. Roughly speaking, to solve a given problem, we need to solve the different parts of it (the subproblem), and from the solutions of the subproblem we get the solution of the original problem. Dynamic programming is often used to optimize recursive problems, such as Fibonacci sequence. If the recursive method is used to solve many of the same sub-problems, the calculation amount can be reduced by using the idea of dynamic programming.

In general, many subproblems are very similar, so the dynamic programming method tries to solve each subproblem only once, thus reducing the amount of computation: once the solution of a given stator problem has been calculated, it is stored in memory so that the next time the solution of the same subproblem is needed, it can be directly looked up in the table. This approach is particularly useful when the number of repeating subproblems increases exponentially with respect to the size of the input.

Suitable for beginners to use animation to simply understand what is dynamic programming: comic interpretation: what is dynamic programming?

1. Three key points of dynamic planning:

  • Optimal substructure (big problems broken down into small problems)
  • Boundary (initial conditions)
  • State transition equation (expressed as an expression)

2. When is dynamic programming needed

  • Overlapping subproblem
  • Optimal substructure
  • Optimal recursive

3. Dynamic programming solution

  • The core idea is recursion.
  • The hard part is figuring out the statedp[i]What does it mean, thenConstruct the state transition matrix, and the final result is recursed using initial conditions.
  • The results of small problems are usually recorded by drawing a table, and then the results of large problems are calculated according to the results of small problems.

4. No aftereffect

The future has nothing to do with the past. That is to say, the result of the calculation of the subproblem will not be changed by future factors.

Second, leetcode programming exercises

1. Climbing stairs: The best Introduction to Dynamic Programming (LeetCode 70)

Suppose a person is climbing stairs. It takes n steps to reach the top. Climb one or two steps at a time. How many different ways can you climb to the top of a building?

Dynamic programming drawing table

Number of steps 0 1 2 3 4 5 6 7 8 9 10
Number of moves 0 1 2 3 5 8 13 21 34 55 89
  • Optimal substructure: F(n-1), F(n-2)
  • Boundaries: F(0) = 0, F(1) = 1, F(2) = 2
  • State transition equation: F(n) = F(n-1) + F(n-2)

code


/** * Method 1: recursion * Disadvantages: High time complexity * Time: O(2^n) space: O(1) *@param {number} n 
 */
function comput1 (n) {
    if (n === 0) {return 0; }else if (n === 1) {return 1; }else if (n === 2) {return 2; }return comput(n - 1) + comput(n - 2);
}

/** * Method 2: Cache (memo) * Disadvantage: requires a map map * time: O(n) space: O(n) *@param {number} n 
 */
function comput2 (n) {
    const map = {0: 0.1: 1.2: 2};
    return computInner(n);
    function computInner(n) {
        if (map[n] === undefined) {
            map[n] = computInner(n - 1) + computInner(n - 2);
        }
        returnmap[n]; }}/ * * * method 3: dynamic equation of state of * : F (n) = F (n - 1) + F (n - 2) * time: O (n) space: O (1) *@param {number} n 
 */
function comput3 (n) {
    if (n === 0) {return 0; }else if (n === 1) {return 1; }else if (n === 2) {return 2; }let pree = 1, pre = 2, temp = 0;
    for (let i = 3; i <= n; i++) {
        temp = pree + pre;
        pree = pre;
        pre = temp;
    }
    return temp;
}


console.log(comput3(4));
console.log(comput3(10));
Copy the code

2. House robbery (LeetCode 198)

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.

The sample

Input: [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.

subproblems

  • If you just think about the first two rooms, who’s going to vote for who
  • Consider a third room
    • If the third room is stolen, it means that the second room is not invested, which is the value of the third room + the amount of the first room
    • If the third room is not stolen, the amount is equal to the amount of the first two rooms
    • Take the larger of the two options

The initial conditions

dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
Copy the code

Draw table

Index I 0 1 2 3 4
dp[i] 2 7 9 10 12

State transition equation

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

code

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

3. Minimum path sum of triangles (2D Dynamic Programming LeetCode 120)

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: input: triangle = [[2], [3,4], [6,5,7], [4,1,8,3]] output: 11

2
3 4
6 5 7
4 1 8 3
Copy the code

The minimum sum of paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).

Minj =03{mini=03{F(i-1, j), F(i-1, I)} + a[I, j]} 3{mini=03{F(i-1, j)} + a[I, j]}

Draw table

Row \ column 1 2 3 4
1 2 – – –
2 5 6 – –
3 11 10 13 –
4 14 11 18 16

code

/ * * *@param {number[][]} triangle
 * @return {number}* /
var minimumTotal = function(triangle) {
    let pre = triangle[0], cur = [].concat(pre);
    for (let i = 1; i < triangle.length; i++) {
        const row = triangle[i];
        for (let j = 0; j < row.length; j++) {
            const value = row[j];
            if (j === 0) {
                cur[j] = pre[j];
            } else if(j === row.length - 1) {
                cur[j] = pre[j - 1];
            } else {
                cur[j] = Math.min(pre[j], pre[j - 1]);
            }
            cur[j] += value; 
        }
        pre = [].concat(cur);
    }
    return Math.min.apply(null, cur);
};
Copy the code

4. Dig

Problem: One country discovered five gold mines, each with a different amount of gold and a different number of workers needed to dig. The total number of miners involved was 10. Every gold mine must be dug up completely or not dug up at all. You can’t send half your men to dig up half of it. I’m going to ask you to use the program to figure out, in order to get as much gold as possible, which gold mines should I dig?

Ore reserves 400 500 200 300 350
Number of workers 5 5 3 4 3

Draw table

A gold mine

Two gold

Gold mine \ Worker 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 400 400 400 400 400 400
2 0 0 0 0 500 500 500 500 500 900

Three gold

Gold mine \ Worker 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 400 400 400 400 400 400
2 0 0 0 0 500 500 500 500 500 900
3 0 0 200 200 500 500 500 700 700 900

Four, five gold mines

Gold mine \ Worker 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 400 400 400 400 400 400
2 0 0 0 0 500 500 500 500 500 900
3 0 0 200 200 500 500 500 700 700 900
4 0 0 200 300 500 500 500 700 800 900
5 0 0 350 350 500 550 650 850 850 900

State transition equation

Assume that the number of gold mines is N, the total number of workers is W, the gold quantity array g[], and the ore quantity array P []

Equation of state: F (n, w) = Max (F (n – 1 w), F (n – 1 w – p [4]) + g] [n – 1)

Time: O(2^n) Space: O(1)

code

/** * Method 2: Dynamic programming * Assume that the number of gold mines is N, the total number of workers is W, the gold quantity array g[], the mine quantity array P [] * state transition equation: F (n, w) = Max (F (n - 1 w), F (n - 1 w - p [4]) + g] [n - 1) * time: O (2 ^ n) space: O (1) *@param {Array<{gold: Number, worker: Number}>} list gold mines and required workers *@param {Number} N Total number of workers */
function work2 (list, w) {
    const n = list.length;
    let pre = [];
    const result = [];
    result.length = pre.length = w + 1;
    pre.fill(0);
    result.fill(0);
    // Fill the boundary
    for (let j = 0; j <= w; j ++) {
        pre[j] = list[0].worker > j ? 0 : list[0].gold;
    }
    // Fill the remaining cells, the outer loop is the number of gold, the inner loop is the number of workers
    for (let i = 0; i < n; i ++) {
        for (let j = 1; j <= w; j ++) {
            if (list[i].worker > j) {
                result[j] = pre[j];
            } else {
                const gold = list[i].gold + pre[j - list[i].worker]; // Dig the I mine, the rest dig the previous mine
                result[j] = Math.max(pre[j], gold);
            }
        }
        pre = [].concat(result);
    }
    return result[w];
}

const list = [
    {gold: 400.worker: 5},
    {gold: 500.worker: 5},
    {gold: 200.worker: 3},
    {gold: 300.worker: 4},
    {gold: 350.worker: 3},];console.log(work2(list, 10));
Copy the code

5. Dungeon games (no aftereffect LeetCode 174)

Some demons captured the princess (P) and locked her in the lower right corner of the dungeon. Dungeons are two-dimensional grids of M x N rooms. Our heroic knight (K), originally placed in the upper left room, must traverse the dungeon and save the princess by fighting demons.

The knight’s initial health point is a positive integer. If his health point drops to zero or below at any point, he dies immediately.

Some rooms are guarded by demons, so the knight loses health points when entering these rooms (if the value in the room is _ negative integer _, the knight loses health points); The other rooms are either empty (the value in the room is 0) or contain orbs that increase the knight’s health points (if the value in the room is _ positive integer _, the knight will increase his health points).

In order to reach the princess as quickly as possible, the knight decided to move only one step to the right or down at a time.

For example, considering the following layout of dungeons, if the knight follows the best path right -> right -> down -> down, the knight’s initial health point is at least 7.

Description:

  • There is no upper limit to how many health points a knight can earn.
  • Any room can be a threat to or increase the knight’s health points, including the upper left room where the knight enters and the lower right room where the princess is imprisoned.

Analysis of the

If the dynamic programming is carried out in the order from the top left to the bottom right, we cannot directly determine the scheme to reach the end point, because two parameters of the same importance influence the subsequent decision at the same time. In other words, such dynamic programming is not satisfied with no aftereffect.

So let’s think about dynamic programming from the bottom right to the top left. Let dp[I][j]dp[I][j] represent the minimum initial value required from coordinates (I,j)(I,j) to the endpoint. In other words, when we reach the coordinates (I,j)(I,j), if our path sum at this point is not less than dp[I][j]dp[I][j], we will reach our destination.

Dp [I][j] represents the minimum initial value required from the coordinates (I,j)(I,j) to the endpoint. In other words, when the coordinates (I,j)(I,j) are reached, if the sum of the paths at this time is not less than dp[I][j], the destination is reached.

Draw table

7 5 2
6 11 5
1 1 6

State transition equation

F(i, j) = max { min{ F(i + 1, j), F(i, j + 1) } - a[i][j], 1 }
Copy the code

code

/ * * *@param {number[][]} dungeon
 * @return {number}* /
var calculateMinimumHP = function(dungeon) {
    let pre = [], cur = [];
    const rows = dungeon.length - 1;
    for (let i = rows; i >= 0; i --) {
        const row = dungeon[i];
        const columns = row.length;
        for (let j = columns - 1; j >= 0; j --) {
            const value = row[j];
            if (i === rows && j === columns - 1) {
                cur[j] = Math.max(1 - value, 1);
            } else if (i === rows) {
                cur[j] = Math.max(cur[j + 1] - value, 1);
            } else if (j === columns - 1) {
                cur[j] = Math.max(pre[j] - value, 1);
            } else {
                cur[j] = Math.max(Math.min(cur[j + 1], pre[j]) - value, 1);
            }
        }
        pre = [].concat(cur);
    }
    return cur[0];
};

Copy the code

reference

  • Comics: What is Dynamic programming?
  • Leetcode | dynamic planning project practice
  • Leetcode antithesis