Very concise C++ code (DP with explanation)


  • 0
    G

    From any element in the matrix, we either can go right or bottom and that is the recursive equation:
    if (dp[i][j] == -1) dp[i][j] = grid[i][j] + min(_minPathSum(grid, i + 1, j, dp), _minPathSum(grid, i, j + 1, dp));

    Two base conditions:

    1. We hit the matrix row/column limits. Returning INT32_MAX enables us to use the recursive equation without any modifications since we are trying to compute the minimum path sum.
      if (i >= grid.size() || j >= grid[0].size()) return INT32_MAX;
    2. We reach the bottom right element.
      if (i == grid.size() - 1 && j == grid[0].size() - 1) return grid[i][j];

    Here is the code:

    int minPathSum(vector<vector<int>>& grid) {
            vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), -1));
            return _minPathSum(grid, 0, 0, dp);
        }
        int _minPathSum(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& dp) {
            if (i >= grid.size() || j >= grid[0].size()) return INT32_MAX;
            if (i == grid.size() - 1 && j == grid[0].size() - 1) return grid[i][j];
            if (dp[i][j] == -1) dp[i][j] = grid[i][j] + min(_minPathSum(grid, i + 1, j, dp), _minPathSum(grid, i, j + 1, dp));
            return dp[i][j];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.