leetcode-minimum path sum

属于中规中矩的dp。和unique paths类似。一次ac。

但是可以通过滚动数组来节省存储空间。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     int minPathSum(vector<vector<int> > &grid) {
 9         vector<vector<int>> dp(grid);
10         int sum = 0;
11         int row = grid.size();
12         int col = grid[0].size();
13         for (int i = 0; i < grid.size(); i++)
14         {
15             sum += grid[i][0];
16             dp[i][0] = sum;
17         }
18         sum = dp[0][0];
19         for (int i = 1; i < grid[0].size(); i++)
20         {
21             sum += grid[0][i];
22             dp[0][i] = sum;
23         }
24         for (int i = 1; i < grid.size(); i++)
25         {
26             for (int j = 1; j < grid[0].size(); j++)
27             {
28                 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
29             }
30         }
31         return dp[row-1][col-1];
32     }
33 };
34 
35 int main()
36 {
37     Solution s;
38     vector<vector<int>> vv = { { 1, 2, 3 }, { 4, 5, 6 } };
39     cout<<s.minPathSum(vv)<<endl;
40     return 0;
41 }