LeetCode: Minimum path sum of triangles

Minimum path sum of a triangle

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.

Such as:

Input: Triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: As shown in the diagram below: 2 3 4 6 5 7 4 1 8 3 The minimum sum of the top-down paths is 11 (i.e., 2 + 3 + 5 + 1 = 11).Copy the code

Source: LeetCode link: leetcode-cn.com/problems/tr… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

---

Recursive depth-first search

Get the first glance of the topic, “triangle”, “path minimum”, I am afraid it is not a depth-first search, this I must hit hard!!

Depth-first search:

Depth-first search is a graph algorithm, which is a graph and tree traversal algorithm. It uses depth-first search algorithm to generate the corresponding topological sorting list of the target graph, and the topological sorting list can be used to solve many related graph theory problems, such as the maximum path problem. As shown in figure:Copy the code

Based on depth-first search, you can calculate the size of each path to the end point, and then iterate over the resulting set to return the smallest path.

class Solution {
    List<Integer> sumList = new ArrayList<>();
    public int minimumTotal(List<List<Integer>> triangle) {
        minimumTotal1(triangle,0.0.0);
        Integer integer = sumList.get(0);
        for (int i = 1; i < sumList.size(); i++) {
            integer = Math.min(integer,sumList.get(i));
        }
        return integer;
    }
    
    public void minimumTotal1(List<List<Integer>> triangle,int i,int j, int sum){
        if(i>=triangle.size()){
            sumList.add(sum);
            return;
        }
        if(j>triangle.get(i).size()){
            sumList.add(sum);
            return;
        }
        Integer integer = triangle.get(i).get(j);
        sum+=integer;
        // Go down left
        minimumTotal1(triangle,i+1,j,sum);
        // Go down right
        minimumTotal1(triangle,i+1,j+1,sum);
        sum-=integer;
        return; }}Copy the code

However! Simple ideas are full of surprises! It’s over the time limit!

Depth-first search is particularly cumbersome in the case of large data volumes!!

---

Dynamic programming

Ideas:

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

As far as the base data of a triangle is concerned, all the data above it are intermediate states in which the final result is obtained.

Then the bottom edge analysis of the above figure:

• For the leftmost “4”, it can only be added to the data on the left side of the triangle, that is, the path: 2->3->6->4
• For the “3” on the right, it can only be added to the data on the right side of the triangle, that is, the path: 2->4->7->3
• The other data on the bottom edge, take 1 as an example: the smallest data from “2” down to “6” and “5” plus itself, that is, 2->3->6 and 2->3->5 and 2->4->5 and the smallest;

Above, we can obtain several state transition formulas:

The leftmost state transition formula:

The rightmost state transition formula:

Other locations:

According to the above formula, the minimum sum of each data of all bottom edges is traversed first; It then iterates through the result set, returning the smallest sum.

public int minimumTotal(List<List<Integer>> triangle) {
    // the sum of row I and column j
    final int size = triangle.size();
    int [][] f = new int[size][triangle.get(size -1).size()];
    f[0] [0] = triangle.get(0).get(0);
    for (int i = 1; i < size; i++) {
        List<Integer> integers = triangle.get(i);
        f[i][0] = f[i-1] [0] + integers.get(0);
        for (int j = 1; j < integers.size(); j++) {
           f[i][j] = Math.min(f[i-1][j-1],f[i-1][j]) + integers.get(j);
        }
        f[i][integers.size()-1] = f[i-1][integers.size()-2]+ integers.get(integers.size()-1);
    }
     int min = f[size -1] [0];for (int i = 1; i < size; i++) {
        min = Math.min(min,f[size -1][i]);
    }
    return min;
}
Copy the code

---

Record daily thoughts and ideas of brushing Leetcode; Witness every bit of growth; Online squat praise link boss! Thumb up!Copy the code