28
07/2015
[LeetCode] 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.
解题思路:
这道题找到从左上角到右下角最小路径长度。每个方格有一个值,路径只能往右走或者往下走。
用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]; } };
转载请注明:康瑞部落 » [LeetCode] Minimum Path Sum
0 条评论