【动态规划】路径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).

从第一行向下走，每次可以走三个位置，走到最后一行，求最小路径和

注意初始化即可：

dp[i][j]=INF

dp下标为1表示g[0]，dp[0][j]=0(避免了边界讨论)

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;
   }
}