preface

“This is the 25th day of my participation in the August Gwen Challenge.

  1. Minimum sum of descent paths
  2. Descent path minimum and II

Minimum sum of descent paths

Given a matrix of square integers of n x n, find and return the minimum sum **** of the descending paths ** through the matrix.

The descent path can start with any element in the first row and select one element from each row. The element selected in the next row is at most one column away from the element selected in the current row (that is, the first element directly below or diagonally to the left or right). Specifically, the next element of the position (row, col) should be (row + 1, col-1), (Row + 1, col), or (Row + 1, col + 1).

 

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]] output: 13 explanation: the following are the two and smallest descent paths, highlighted in bold + italics: ,1,3,1,3 [[2], [[2], [6,5,4],,5,4 [6], [7,8,9]],8,9 [7]]Copy the code

Thought analysis

Because the element selected in the next row is at most one column apart from the element selected in the current row

The descent path of position (I,j) is only related to the adjacent elements in the previous row (i-1, J-1) (i-1,j) (i-1,j+1)

Define the dp array dp[I][j] represents the minimum path to the current element

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j + 1]) + matrix[i][j]

AC code:

   public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[2][n];

        for(int j=0; j<n; j++) dp[0 & 1][j] = matrix[0][j];

        for(int i=1; i<m; i++){for(int j=0; j<n; j++){int left = j-1> =0? dp[(i-1) & 1][j-1] : Integer.MAX_VALUE;
                int right = j+1 < n? dp[(i-1) & 1][j+1]:Integer.MAX_VALUE;

                dp[i & 1][j] = Math.min(dp[(i-1) & 1][j], Math.min(left, right)) + matrix[i][j]; }}int ans = Integer.MAX_VALUE;

        for(int j=0; j<n; j++) ans = Math.min(ans, dp[(m-1) & 1][j]);

        return ans;
    }
Copy the code

Descent path minimum and II

Given a square arR array of integers, define the “non-zero offset drop path” to select a number from each row of the ARR array, where the adjacent numbers are not in the same column of the original array.

Return the minimum sum of the non-zero offset drop paths.

Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]] output: 13 explanation: all non-zero offset descent paths include: [1, 9], [1, 5, 7], [1, 6],,6,8 [1], [2,4,8],,4,9 [2], [2, 6],,6,8 [2], [3,4,8], [3,4,9], [3, 5, 7], [3,5,9] the smallest numeric sum in the descent path is [1,5,7], so the answer is 13.Copy the code

 

Tip:

  • 1 <= arr.length == arr[i].length <= 200
  • -99 <= arr[i][j] <= 99

Analysis of ideas:

The solution is similar to the previous problem, because the element selected in the next row cannot be in the same column as the element selected in the current row

So position (I,j) depends on everything in the previous row except position (I -1,j)

dp[i][j] = min(dp[i-1][x] ….) (x ! = j)

Triple for loop

In fact, I only care about the minimum and subminimum of the previous row

AC code:

Replace the 3-fold for loop with a finite number of variables

    public int minFallingPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

 
        int[][] dp = new int[m][n];

        int minIndex1 = -1;
        int minIndex2 =-1;

        for(int j=0; j<n; j++){ dp[0][j] = grid[0][j];
            if(grid[0][j] < (minIndex1 == -1 ? Integer.MAX_VALUE:grid[0][minIndex1])){
                minIndex2 = minIndex1;
                minIndex1 = j;
            }else if(grid[0][j] < (minIndex2 == -1 ? Integer.MAX_VALUE:grid[0][minIndex2])){ minIndex2 = j; }}for(int i=1; i<m; i++){int curMinIndex1 = -1;
            int curMinIndex2 = -1;
            for(int j=0; j<n; j++){if(j == minIndex1){
                    dp[i][j] = grid[i][j] + dp[i-1][minIndex2];
                }else{
                    dp[i][j] = grid[i][j] + dp[i-1][minIndex1];
                }

                if(dp[i][j] < (curMinIndex1 == -1 ? Integer.MAX_VALUE:dp[i][curMinIndex1])){
                    curMinIndex2 = curMinIndex1;
                    curMinIndex1 = j;
                }else if(dp[i][j] < (curMinIndex2 == -1 ? Integer.MAX_VALUE:dp[i][curMinIndex2])){
                    curMinIndex2 = j;
                }
            }
            minIndex1 = curMinIndex1;
            minIndex2 = curMinIndex2;
        }

        int ans = Integer.MAX_VALUE;

        for(int j=0; j<n; j++) ans = Math.min(ans, dp[m -1][j]);

        return ans;
    }
Copy the code