110. Minimum Path Sum

class Solution { public: /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum(vector<vector<int>> &grid) { // write your code here // DP const int m = grid.size(); if(m == 0){ return 0; } const int n = grid[0].size(); //vector<vector<int>> dp(m, vector<int>(n, 0)); //vector<vector<int>> dp(2, vector<int>(n, INT_MAX)); vector<int> dp(n, INT_MAX); dp[0] = 0; //dp[0][0] = grid[0][0]; //for(int i = 1; i < m; i++){ // dp[i][0] = dp[i - 1][0] + grid[i][0]; //} //for(int j = 1; j < n; j++){ // dp[0][j] = dp[0][j - 1] + grid[0][j]; //} for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(j == 0){ dp[j] += grid[i][j]; } else{ dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]; } //dp[i % 2][j] = min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]) + grid[i][j]; } } //return dp[(m - 1) % 2][n - 1]; return dp[n - 1]; } };