LeetCode:Minimum Path Sum最短路径

核心思想：动态规划

• 这是一道经典的基础动态规划题目。给你一个二维数组的方阵,初始点在左上角,只允许你往左或者往下走,不能走其他方向,目的地是右下角,希望你找出一条最短的路径.
• 注意点:要注意边界的处理.
• 大体思路:同时创建一个新的二维数组保存当前最优情况的值,这就是动态规划的精髓,充分利用之前计算的结果.在考虑一个点的时候,拿到它这个点之前点的最优值然后加上当前点就是这个点当前状态下的最优解,依次类推到最后,可以得出遍历结束后的最优解.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        if(n == 0) return 0;
        if(m == 0) return 0;
        vector<vector<int>> dp(grid);
        int i;
        int j;
        for( i = 0;i < n ; ++i)
        {
            for(j = 0; j < m; ++j)
            {
                if(i==0 && j==0) dp[0][0] = grid[0][0];
                else if(i == 0) dp[0][j] = grid[0][j] + dp[0][j-1];
                else if(j == 0) dp[i][0] = grid[i][0] + dp[i-1][0];
                else dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};