931. 下降路径最小和_DP

int minFallingPathSum2(vector<vector<int>>& A) {
    int row = A.size();
    if(row == 0) return 0;
    if(row == 1) return A[0][0];
    int col = A[0].size();

    vector<vector<int>> dp(row+1,vector<int> (col+1,INT32_MAX));
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            if(i==0) dp[i][j] = A[i][j];
            else{
                if(j==0) dp[i][j] = min(dp[i-1][j],dp[i-1][j+1])+A[i][j];
                else if(j==col-1) dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+A[i][j];
                else dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j+1],dp[i-1][j]))+A[i][j];
            }
        }
    }
    return *min_element(dp[row-1].begin(),dp[row-1].end());
}

int minFallingPathSum3(vector<vector<int>>& A) {
    int row = A.size();
    if(row == 0) return 0;
    if(row == 1) return A[0][0];
    int col = A[0].size();

    vector<int> dp(col+1,INT32_MAX);
    vector<int> dp2(col+1,INT32_MAX);

    for(int i=row-1;i>=0;i--){
        for(int j=0;j<col;j++){
            if(i==row-1) dp[j] = A[i][j];
            else{
                if(j==0){
                    dp[j] = min(dp2[j],dp2[j+1]) + A[i][j];
                }else if(j==col-1){
                    dp[j] = min(dp2[j],dp2[j-1]) + A[i][j];
                }else{
                    dp[j] = min(dp2[j-1],min(dp2[j+1],dp2[j]))+A[i][j];
                }
            }
        }
        if(i!=0) swap(dp,dp2);
    }
    return *min_element(dp.begin(),dp.end());
}

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
	    int row = A.size();
	    if(row == 0) return 0;
	    if(row == 1) return A[0][0];
	    int col = A[0].size();
	
	    vector<int> dp(col+2,INT32_MAX);
	    vector<int> dp2(col+2,INT32_MAX);
	
	    for(int i=1;i<row+1;i++){
	        for(int j=1;j<col+1;j++){
	            if(i==1) dp[j] = A[i-1][j-1];
	            else{
	                dp[j] = min(dp2[j-1],min(dp2[j+1],dp2[j]))+A[i-1][j-1];
	            }
	        }
	        if(i!=row) swap(dp,dp2);
	    }
	    return *min_element(dp.begin(),dp.end());
	}
};