64 Minimum Path Sum

dp[row - 1][col - 1] 表示从 [0][0] 到 [row-1][col-1] 位置上加起来的最小的和。所以dp递推公式如下：

• dp[x,y] = grid[x][y] + max{ dp[x-1][y], dp[x][y-1] } , x>=1, y>=1
• dp[0][0] = grid[0][0]
• dp[0][y] = dp[0][y-1] + grid[0][y], y>=1
• dp[x][0] = dp[x-1][0] + grid[x][0], x>=1

最后的结果就是：dp[row-1][col-1]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = (int)grid.size();
        
        if (row == 0)
        {
            return 0;
        }
        
        int col = (int)( grid[0].size() );
        
        if (col == 0)
        {
            return 0;
        }
        
        // make sure row >= 1 && col >= 1
        for (int i = 1; i < col; i++)
        {
            (grid[0])[i] = (grid[0])[i - 1] + (grid[0])[i];
        }
        
        for (int i = 1; i < row; i++)
        {
            (grid[i])[0] = (grid[i-1])[0] + (grid[i])[0];
        }
        
        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < col; j++)
            {
                (grid[i])[j] = (grid[i])[j] + min(grid[i-1][j], grid[i][j-1]);
            }
        }
        
        return grid[row-1][col-1];
    }
};