Minimum Path Sum LeetCode solution in C++

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