LeetCode OJ--Minimum Path Sum **

https://oj.leetcode.com/problems/minimum-path-sum/

对一个grid从左上角到右下角的路径，求出路径中和最小的。

受之前思路的影响，就寻思递归，并且记录中间过程的数据，这样避免重复计算。但是超时了。

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        vector<vector<int> > sum;
        if(grid.size()==0)
            return 0;
        int row = grid.size();
        int col = grid[0].size();
        sum.resize(row);
        for(int i = 0;i<row;i++)
            sum[i].resize(col);
        return calcPath(0,0,grid,row,col,sum);
    }
    int calcPath(int xPos,int yPos,vector<vector<int> > &grid,int row,int col, vector<vector<int> > &sum)
    {
        if(xPos == row-1 && yPos == col-1)
            return grid[xPos][yPos];
        int min1 = -1,min2 = -1;
        if(xPos < row-1)
            if (sum[xPos+1][yPos] == 0)
                min1 = calcPath(xPos+1,yPos,grid,row,col,sum);
            else
                min1 = sum[xPos+1][yPos];
        if(yPos < col-1)
            if(sum[xPos][yPos+1] == 0)
                min2 = calcPath(xPos,yPos+1,grid,row,col,sum);
            else
                min2 = sum[xPos][yPos+1];
        if(min1 == -1)
            return min2;
        if(min2 == -1)
            return min1;
        return min1<min2?min1:min2;
    }
};

其实，这个递归也是动态规划的思想。

但是，动态规划也可以用for循环做，于是清理思路，动态规划，for循环实现。

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        vector<vector<int> > sum;
        if(grid.size()==0)
            return 0;
        int row = grid.size();
        int col = grid[0].size();
        sum.resize(row);
        for(int i = 0;i<row;i++)
            sum[i].resize(col);

        //initialize
        sum[row-1][col-1] = grid[row-1][col-1];
        for(int i = col-2;i>=0;i--)
            sum[row-1][i] += grid[row-1][i] + sum[row-1][i+1];
        for(int i = row-2;i>=0;i--)
            sum[i][col-1] += grid[i][col-1] + sum[i+1][col-1];

        for(int i = row-2; i>=0;i--)
            for(int j = col-2;j>=0;j--)
            {
                int t1 = grid[i][j] + sum[i][j+1];
                int t2 = grid[i][j] + sum[i+1][j];
                sum[i][j] = t1<t2?t1:t2;
            }
        return sum[0][0];
    }
 
};