leetcode第一刷_Minimum Path Sum

能够用递归简洁的写出，可是会超时。

dp嘛。这个问题须要从后往前算，最右下角的小规模是已知的，边界也非常明显，是最后一行和最后一列，行走方向的限制决定了这些位置的走法是唯一的，能够先算出来。然后不断的往前推算。

用distance[i][j]保存从当前位置走到最右下角所需的最短距离，状态转移方程是从distance[i+1][j]和distance[i][j+1]中选一个小的，然后再加上自身的。

代码非常easy理解，这就是dp的魅力。空间上是能够优化的，由于当前状态仅仅与后一行和后一列有关系。

class Solution {

public:

    int minPathSum(vector<vector<int> > &grid) {

        int erow = grid.size();

        if(erow<=0)  return 0;

        int ecolumn = grid[0].size();

        if(ecolumn<=0)   return 0;

        if(erow==1&&ecolumn==1) return grid[0][0];

        vector<int> tpres(ecolumn, 0);

        vector<vector<int> > distance(erow, tpres);

        distance[erow-1][ecolumn-1] = grid[erow-1][ecolumn-1];

        for(int i=erow-2;i>=0;i--)

            distance[i][ecolumn-1] = distance[i+1][ecolumn-1] + grid[i][ecolumn-1];

        for(int i=ecolumn-2;i>=0;i--)

            distance[erow-1][i] = distance[erow-1][i+1] + grid[erow-1][i];

        for(int i=erow-2;i>=0;i--){

            for(int j=ecolumn-2;j>=0;j--){

                distance[i][j] = min(distance[i+1][j], distance[i][j+1])+grid[i][j];

            }

        }

        return distance[0][0];

    }

};