Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

思路

很简单的动态规划问题，用一个和grid数组一样大的数组，来存储前一次的状态。 当前元素的左侧元素和上方元素的最小路径和，再加上当前元素的值，就是当前元素的最短路径值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = 0;
        if(row > 0) col = grid[0].size();
        vector<vector<int>> dp(row);
        for(int i = 0; i < row; i++){
            dp[i].resize(col);
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(i == 0 && j == 0) dp[i][j] = grid[i][j];
                else{
                    if(i == 0){
                        dp[i][j] = grid[i][j] + dp[i][j-1];
                    }
                    else if(j == 0){
                        dp[i][j] = grid[i][j] + dp[i-1][j];
                    }
                    else{
                        dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
                    }
                }
            }
        }
        return dp[row-1][col-1];
    }
};