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.
简单的动态规划题。刚开始又写成路径和了……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
class
Solution {public: int
minPathSum(vector<vector<int> > &grid) { vector<int> p(grid.size(),0); p[0] = grid[0][0]; for(int
i = 1; i < grid.size();i++) p[i] = p[i-1] + grid[i][0]; for(int
i =1; i < grid[0].size();i++) { p[0] = p[0]+grid[0][i]; for(int
j = 1 ; j < grid.size();j++) { p[j] = min(p[j],p[j-1]) + grid[j][i]; } } return
p[grid.size()-1]; }}; |
Minimum Path Sum,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3595803.html