# Leetcode 931. Minimum Falling Path Sum
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/minimum-falling-path-sum/ 。

想法 :

類似走樓梯的DP，只是變成二維並由上往下走。

時間複雜度 : O(r*c)。

程式碼 :

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int r=matrix.size(), c=matrix[0].size(), ans[110][110]={0}, ansi=INT_MAX, dir[3]={-1, 0, 1};
        
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                ans[i][j]=11000;
            }
        }
        
        for(int i=0 ; i<c; i++){
            ans[0][i]=matrix[0][i];
        }
        
        for(int i=1 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                int c1=j+dir[0], c2=j+dir[1], c3=j+dir[2];
                 
                if(c1 >= 0 && c1 < c){
                    ans[i][j]=min(ans[i][j], ans[i-1][c1]);    
                }
                
                if(c2 >=0 && c2 < c){
                    ans[i][j]=min(ans[i][j], ans[i-1][c2]);    
                }
                
                if(c3 >= 0 && c3 < c){
                    ans[i][j]=min(ans[i][j], ans[i-1][c3]);    
                }
                
                //cout << ans[i][j] << endl;
                ans[i][j]+=matrix[i][j];
            }
        }
        
        /*for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                printf(" %2d",ans[i][j]);
            }
            cout << endl;
        }*/
        
        for(int i=0 ; i<c ; i++){
            ansi=min(ansi,ans[r-1][i]);
        }
        
        return ansi;
    }
};