Leetcode question brushing series -- 931. Minimum sum of descent path

To give you one n x n Of square An array of integers  matrix , Please find out and return through matrix The descent path Of Minimum and .

descent path You can start with any element in the first line , And select an element from each row . The element selected in the next row is at most one column apart from the element selected in the current row （ That is, the first element directly below or diagonally left or right ）. say concretely , Location (row, col) The next element of should be (row + 1, col - 1)、(row + 1, col) perhaps (row + 1, col + 1) .

Example 1：

Input ：matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output ：13
explain ： As shown in the figure , And the smallest two descent paths
Example 2：

Input ：matrix = [[-19,57],[-40,-5]]
Output ：-59
explain ： As shown in the figure , Is the minimum descent path

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-falling-path-sum
 

Ideas ：

 Define a two-dimensional array  dp[][] ,dp[i][j]  From the first line to the current element  matrix[i][j]  Descent path and minimum value .
 set up  matrix  The number of rows is  rowLen,  The number of columns is  colmLen
1.  initialization 
   dp[0][j] = matrix[0][j]
2.  State shift 
   1) j>0 && j< colmLen - 1
      dp[i][j] = min(dp[i-1][j-1], dp[i-1][j],dp[i-1][j+1]) + matrix[i][j]
   2) j == 0
      dp[i][j] = min(dp[i-1][j],dp[i-1][j+1]) + matrix[i][j]
   3) j == colmLen - 1
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + matrix[i][j]
3.  Traverse  i == rowLen  The elements of , Find the minimum , That's what the title asks for 

java Code ：

class Solution {
    public int minFallingPathSum(int[][] matrix) {
    int rowLen = matrix.length;
        int colmLen = matrix[0].length;

        int[][] dp = new int[rowLen][colmLen];

        // 1.  initialization 
        for(int j=0;j<colmLen;j++) {
            dp[0][j] = matrix[0][j];
        }
        // 2.  State shift 

        for(int i=1;i<rowLen;i++) {
            for(int j=0;j<colmLen;j++) {
                                if(j==0) {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j+1]) + matrix[i][j];
                } else if(j==colmLen-1) {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + matrix[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]);
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j+1]) + matrix[i][j];
                }
            }
        }

        // 3.  Traverse to find the minimum 
        int result = Integer.MAX_VALUE;
        for(int j=0;j<colmLen;j++) {
            result = Math.min(result,dp[rowLen-1][j]);
        }
        
        return result;
    }
}