Minimum Path Sum - 2D Dynamic Programming

My approach:

In questions involving grids or 2D arrays, we have a variety of questions.

In this question, if you observe we have a fixed starting point and a fixed ending point.

This question cannot be solved using the greedy approach, hence we need to use recursion to try all possible answers and eventually, we need to come up with an iterative solution.

My solution:

• Recursive

• Iterative

Code:

• Recursion with Memoization

  Time complexity: O(n^2)

  Space complexity: O(n^2)

class Solution {
public:

    int helper(vector<vector<int>>& grid, int m, int n, int i, int j, vector<vector<int>>& dp){

        if(i>=m || j>=n){
            return 1e8;
        }

        if(i==m-1 && j==n-1){
            return grid[i][j];
        }

        if(dp[i][j]!=-1){
            return dp[i][j];
        }

        int down = helper(grid,m,n,i+1,j,dp);
        int right = helper(grid,m,n,i,j+1,dp);

        dp[i][j] = min(down,right)+grid[i][j];
        return min(down,right)+grid[i][j];
    }

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n,-1));

        return helper(grid,m,n,0,0,dp);
    }
};

• Dynamic Programming

  Time complexity: O(n^2)

  Space complexity: O(n^2)

class Solution {
public:

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n,-1));

        dp[0][0] = grid[0][0];

        for(int i=1;i<m;i++){
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }

        for(int i=1;i<n;i++){
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                int left = dp[i][j-1];
                int up = dp[i-1][j];

                dp[i][j] = min(left, up) + grid[i][j];
            }
        }

        return dp[m-1][n-1];
    }
};

Question Link:

https://leetcode.com/problems/minimum-path-sum/description/