给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例： 输入：[[1,2,3],[4,5,6],[7,8,9]] 输出：12 解释： 可能的下降路径有： [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9] [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9] [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] 和最小的下降路径是 [1,4,7]，所以答案是 12。 提示： 1 <= A.length == A[0].length <= 100 -100 <= A[i][j] <= 100来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-falling-path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这题很简单，DP解题
状态表初始化数值INT_MAX，状态表第一行就是数组本身从第二行开始，每个格子可以接受他头顶的3个（左中右）状态的最小的过来状态方程如下： d p [ i ] [ j ] = A [ i ] [ j ] + m i n ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j + 1 ] ) dp[i][j] = A[i][j]+min(dp[i-1][j-1], \quad dp[i-1][j],\quad dp[i-1][j+1]) dp[i][j]=A[i][j]+min(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])为了方便处理边界，状态表左右各加1列 class Solution { public: int minFallingPathSum(vector<vector<int>>& A) { const int N = A.size(); vector<vector<int>> dp(N,vector<int>(N+2,INT_MAX)); int i, j, minSum = INT_MAX; for(i = 0; i < N; i++) dp[0][i+1] = A[0][i];//初始化第一行 for(i = 1; i < N; ++i) { for(j = 1; j < N+1; ++j) { //注意加了两列后下标的错位 dp[i][j] = A[i][j-1]+min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]); } } for(i = 1; i < N+1; ++i) minSum = min(minSum,dp[N-1][i]);//最后一行最小 return minSum; } }; 状态可以压缩：观察到下一行状态只跟上一行状态有关，所以只需要2行数组空间即可 class Solution { public: int minFallingPathSum(vector<vector<int>>& A) { const int N = A.size(); vector<int> dp(N+2,INT_MAX); vector<int> temp(N+2,INT_MAX); int i, j, minSum = INT_MAX; for(i = 0; i < N; i++) temp[i+1] = A[0][i];//初始化第一行 for(i = 1; i < N; ++i) { for(j = 1; j < N+1; ++j) { //注意加了两列后下标的错位 dp[j] = A[i][j-1]+min(min(temp[j-1],temp[j]),temp[j+1]); } swap(dp,temp); } return *min_element(temp.begin(),temp.end()); } };