[LeetCode] Minimum Path Sum

Minimum Path Sum

Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.

Note:You can only move either down or right at any point in time.

解题思路：

这道题找到从左上角到右下角最小路径长度。每个方格有一个值，路径只能往右走或者往下走。

用DP算法。

d[i][j]表示从0,0到i,j的最短路径长度。那么有递推公式：

d[i][j] = grid[i][j]+min(d[i-1][j], d[i][j-1])。

还得注意边界条件。

下面是程序代码：

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

版权声明：本文为博主原创文章，未经博主允许不得转载。

，要愈合不能，要忘却不能，要再次拥抱，却鼓不起足够的勇气，