LeetCode 931 下降路径最小和

题目描述链接：https://leetcode-cn.com/problems/minimum-falling-path-sum/

解题思路：动态规划。（1）状态表示：dp[i][j]表示到达A[i][j]节点的最小路径。

                                    （2）边界确定：dp[0][j]=A[0][j]即第一行的值为即为本身值，因为第一行为开始。

                                    （3）状态转移方程：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j]，这里由于是从上到下，且最多跨越一列，当然还要考虑越界问题，如果j=0,那么dp[i][j-1]就不用考虑了，当然此时

                                              dp[i][j-1]也不存在，另外j=len-1时也时如此。具体实现可以参考下文代码

最后遍历最后一行的dp[len-1][j],寻找最小值返回即可。

LeetCode C++解题参考代码如下：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int minum=0xfffffff;
        int len=A.size();
        if(len==0){
            return 0;
        }
        int dp[len][len];
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(i==0){
                    dp[i][j]=A[i][j];
                }
                else {
                    if(j-1>=0&&j+1<len){
                        int temp=min(dp[i-1][j],dp[i-1][j-1]);
                        dp[i][j]=min(temp,dp[i-1][j+1])+A[i][j];
                    }
                    
                    else if(j-1>=0){
                        dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+A[i][j];
                    }
                    else if(j+1<len){
                        dp[i][j]=min(dp[i-1][j+1],dp[i-1][j])+A[i][j];
                    }
                    else{
                        dp[i][j]=dp[i-1][j]+A[i][j];
                    }
                }
                
               
            }
        }
        for(int i=0;i<len;i++){
            minum=min(dp[len-1][i],minum);
        }
        return minum;
    }
};