Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

The minimum path sum of the triangle in question 120 is as follows:

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: 11 explanation: as shown in the diagram below: The minimum sum of the top down paths of 2, 3, 4, 6, 5, 7, 4, 1, 8, 3 is 11 (i.e. 2 + 3 + 5 + 1 = 11).Copy the code

Example 2:

Triangle = [[-10]] Output: -10Copy the code

A, thinking

The first thing I thought about this problem was to use recursion. The general idea of recursion is: from top to bottom, select all nodes in turn. The minimum path sum is taken only when the node to the last layer is selected.

The recursive code implementation is shown below:

Unfortunately, using recursion causes timeouts.

So I had to change the solution, so I tried to use dynamic programming to solve this problem.

Dynamic programming

We assume that dp[I][j] is the minimum sum of paths from the vertex to row I and column j.

  1. Edge cases

For the first column, you can only reach it straight down. So dp[I][0] += dp[i-1][0] + triangle. Get (I).get(0)

  1. State transition equation

What does the value of dp[I][j] depend on?

There are two cases:

  • whenj > i-1When,dp[i][j] = triangle.get(i).get(j) + dp[i-1][j-1]. That is, the last element in the next row is, and only the last element in the previous row can be selected
  • Other information:dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + arr[i][j], (i > 0, j > 0)

Finally, we take the minimum value of the last row of dp, and the result is the minimum sum of paths to the last layer

Second, the implementation

The implementation code

The implementation code is exactly the same as in the idea

    public int minimumTotal(List<List<Integer>> triangle) {
        int ret = Integer.MAX_VALUE;
        int m = triangle.size(), n = triangle.get(triangle.size()-1).size();
        int[][] dp = new int[m][n];
        // Initialize the first column
        dp[0] [0] = triangle.get(0).get(0);
        for (int i=1; i<n; i++){
            dp[i][0] += dp[i-1] [0] + triangle.get(i).get(0);
        }
        for (int i=1; i<m; i++){
            for (int j=1; j<=i; j++){
                if (j > i-1){
                    dp[i][j] = triangle.get(i).get(j) + dp[i-1][j-1];
                } else {
                    dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i-1][j], dp[i-1][j-1]); }}}// Minimizes the last line
        for(int i=0; i<n; i++){
            ret = Math.min(ret, dp[m-1][i]);
        }
        return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>(){
            {
                add(Arrays.asList(2));
                add(Arrays.asList(3.4));
                add(Arrays.asList(6.5.7));
                add(Arrays.asList(4.1.8.3)); }}; List<List<Integer>> list1 =new ArrayList<>(){
            {
                add(Arrays.asList(-1));
                add(Arrays.asList(-2, -3)); }};int ret = new Number120().minimumTotal(list);
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section