[dynamic planning] path dp:931 Minimum Falling Path Sum

931. Minimum Falling Path Sum

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Go down from the first line , You can walk three places at a time , Go to the last line , Find the minimum path sum

Pay attention to initialization ：

dp[i][j]=INF

dp Subscript to be 1 Express g[0],dp[0][j]=0( Avoid boundary discussions )

class Solution {
    public int minFallingPathSum(int[][] g) {
    int n=g.length;
    int [][] dp=new int[n+2][n+2];
    for(int i=0;i<=n+1;i++)
    Arrays.fill(dp[i],0x3f3f3f3f);
    for(int i=0;i<=n+1;i++){
        dp[0][i]=0;
    }
    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=Math.min(dp[i][j],Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i-1][j+1]))+g[i-1][j-1]);
          if(i==n){
              res=Math.min(res,dp[i][j]);
          }  
        }
    }
    return res;
   }
}