This is my first article on getting started

preface

There is a client who reads short stories to his daughter every day. From the first seven or eight days, to dozens of days, and now 102 days. Deeply touched, sigh time flies, feeling the client and his daughter’s self-discipline, persistence. So I set a small goal of writing at least one algorithm every day!!

On the recent algorithm encountered common ideas:

1. Various sorting algorithms

2. Pointer and bit processing

3. Dynamic programming

So let’s wrap up dynamic programming today.

concept

The process of an activity is divided into several interrelated stages, each of which makes decisions to maximize the activity of the entire process. This process of optimizing multi-stage decision is called dynamic programming method.

The basic idea of dynamic programming is to decompose the problem into a number of interrelated subproblems, and record the answers of the subproblems with a table, and then get the answer of the original problem from the answers of the subproblems.

2. What’s the difference between the two?

The title

Minimum path sum of triangles

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

Each step can only move to adjacent nodes in the next row. Adjacent nodes in this context are two nodes whose subscripts are the same as or equal to the subscripts +1 of the nodes above. That is, if you are at the index I of the current row, then you can move to the index I or I +1 of the next row.

Example:

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

Analysis of the

  • Find the minimum path sum into a small problem: the sum of any way from the top to the bottom of the triangle.

  • Take out the minimum value of the small problem is the minimum path sum.

Ideas:

F [I][j] represents the sum of paths from the top of triangle to (I,j). (I,j) represents the position of row I and column j numbered from 0. Is expressed by the function:

f[i][j] = Math.min(f[i-1][j-1],f[i-1][j]) + triangle[i][j]

Two special cases:

  • When you get to the far left of line I, you can only go to the far left of line I -1, i.e

    f[i][0]=f[i-1][0]+triangle[i][0]

  • When you get to the right most of row I, you can only go to the right most of row I minus 1, i.e

    f[i][i]=f[i-1][i-1]+triangle[i][i]

The minimum value of f[n-1][0]-f[n-1][n-1] is the minimum path sum, n is the number of rows of triangle.

code

/ * * *@param {number[][]} triangle
 * @return {number}* /
var minimumTotal = function(triangle) {
    let n = triangle.length;
    // Generate a two-dimensional array like triangle with an initial value of 0
    let f = Array.apply(null.Array(n)).map((t, i) = > Array(i + 1).fill(0));
    f[0] [0] = triangle[0] [0];
    // Find the sum of each top and bottom (subproblem)
    for (let i = 1; i < n; ++i) {
        f[i][0] = f[i - 1] [0] + triangle[i][0];
        for (let j = 1; j < i; ++j) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];
    }
    let minTotal = f[n - 1] [0];
    // The optimal solution of the subproblem
    for (let i = 1; i < n; ++i) {
        minTotal = Math.min(minTotal, f[n - 1][i]);
    }
    return minTotal;
};
Copy the code

conclusion

It seems that the general direction of dynamic programming is not very difficult, mainly depends on the thinking of solving the problem:

The problem can be decomposed into a number of interrelated subproblems

Find the answer to the subproblem

Get the optimal solution from the subproblem