Minimum Path Sum

http://www.lintcode.com/en/problem/minimum-path-sum/

Discussion

• 跟Triangl问题思路很接近很接近。DP。
• sum[i][j]表示从[0][0]到[i-1][j-1]的minimum path sum， 状态转移方程为：
  sum[i][j] = min(sum[i-1][j], sum[i][j-1]) + grid[i][j]; 要么从上面下来要么从左边过来
• 初始化的时候先初始化第一行和第一列
• answer：sum[m-1][n-1]

Solution 1

//O(n^2) rum time
//space: O(n)
class Solution {
public:
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n == 0) return 0;
        vector<vector<int> > sum(m, vector<int>(n, 0));
        sum[0][0] = grid[0][0];
        for(int i=1; i<m; i++) {
            sum[i][0] = sum[i-1][0] + grid[i][0];
        }
        for(int j=1; j<n; j++) {
            sum[0][j] = sum[0][j-1] + grid[0][j];
        }

        for(int i = 1; i<m; i++) {
            for(int j = 1; j < n; j++) {
               sum[i][j] = min(sum[i-1][j], sum[i][j-1]) + grid[i][j]; 
            }
        }
        return sum[m-1][n-1];
    }
};

跟Triangle问题一样，画个图很容易降成一维的空间.
sum[j]表示任意一行到达第j列的时候的minimum sum

//Space：O(n)
int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n == 0) return 0;
        vector<int> sum(n, 0);
        sum[0] = grid[0][0];
        for(int i=1; i<n; i++) {
            sum[i] = sum[i-1]+grid[0][i];
        }
        for(int i = 1; i<m; i++) {
            sum[0] += grid[i][0];//在每一行开始的时候update sum[0]
            for(int j = 1; j < n; j++) {
               sum[j] = min(sum[j-1], sum[j]) + grid[i][j]; 
            }
        }
        return sum[n-1];
    }

同样利用grid本身的空间的话可以实现O(1) space