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 }