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

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

想法 :

爬樓梯的DP。
sum[i][j] = min(sum[i-1][j], sum[i][j-1]) + grid[i][j];

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

程式碼 :

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int r=grid.size(), c=grid[0].size(), dp[210][210];
        
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                dp[i][j]=INT_MAX;
            }
        }
        dp[0][0]=0;
        
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                if(i-1 >= 0) dp[i][j]=dp[i-1][j];
                if(j-1 >= 0) dp[i][j]=min(dp[i][j], dp[i][j-1]);
                
                dp[i][j] += grid[i][j];        
            }
        }
        
        /*for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                printf(" %2d", dp[i][j]);
            }
            printf("\n");
        }*/
        
        return dp[r-1][c-1];
    }
};