Day 35, 64 Minimum Path Sum

Minimum Path Sum
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.
-------------------------------------------
Solution #1, Memoization
matrix[i][j] = min(matrix[i][j-1],matrix[i-1][j]) + grid[i][j] 

class Solution {
public:
    int minP (vector<vector<int> > &grid, int row, int col,vector<vector<int> > &mapping) {
        if (mapping[row][col] != -1) {
            return mapping[row][col];
        }
        if (row == 0 && col == 0) {
            mapping[row][col] = grid[0][0];
            return mapping[row][col];
        }
        if (row != 0 && col != 0) {
           mapping[row][col] = min(minP(grid,row-1,col,mapping) + grid[row][col],
                                minP(grid,row,col-1,mapping) + grid[row][col]);
            return mapping[row][col];
        }
        if (row == 0) {
            mapping[row][col] = minP(grid,0,col-1,mapping) + grid[0][col];
            return mapping[row][col];
        }
        mapping[row][col] = minP(grid,row-1,0,mapping) + grid[row][0];
        return mapping[row][col];
    }
    
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = grid.size()-1;
        int n = grid[0].size()-1;
        vector<vector<int> > mapping(m+1);
        for (int i=0;i<m+1;i++) {
            vector<int> v(n+1);
            for (int j=0;j<n+1;j++) {
                v[j] = -1;
            }
            mapping[i] = v;
        }
        return minP(grid,m,n,mapping);
    }
};

Solution #2, DP O(n) space
matrix[i][j] = min(matrix[i][j-1],matrix[i-1][j]) + grid[i][j]

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n+1,INT_MAX);
        dp[1] = 0;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                dp[j+1] = min(dp[j+1],dp[j]) + grid[i][j];
            }
        }
        return dp[n];
    }
};

因为是minimum，所以dp初始为INT_MAX，如果是maximum，则设为INT_MIN
可先做2d-array的dp，再转化为1d. 注意dp[1] = 0
follow up：增加可以往左
见Google interview questions #2 第5题