LeetCode – Refresh – Minimum Path Sum

 1 class Solution {
 2 public:
 3     int minPathSum(vector<vector<int> > &grid) {
 4         if (grid.size() == 0) return 0;
 5         int n = grid.size(), m = grid[0].size();
 6         vector<int> dp(n, 0);
 7         dp[0] = grid[0][0];
 8         for (int i = 1; i < n; i++) dp[i] = dp[i-1] + grid[i][0];
 9         for (int i = 1; i < m; i++) {
10             for (int j = 0; j < n; j++) {
11                 if (j == 0) dp[j] += grid[j][i];
12                 else dp[j] = min(dp[j], dp[j-1]) + grid[j][i];
13             }
14         }
15         return dp[n-1];
16     }
17 };