Unique Paths - 2D Dynamic Programming

My approach:

In this question, we have to start from a fixed point i.e., (0,0) and finish at a fixed point which is (m-1, n-1).

We cannot apply a greedy solution here so we need to solve it using recursion.

To solve the overlapping subproblems of recursion we will memoize it by using a 2d array.

For an iterative solution as well we would require a 2d array to store the results while applying the bottom-up approach at every element.

My solution:

• Recursive

• Iterative

Code:

• Recursion with Memoization:

  Time Complexity : O(n^2)

  Space Complexity : O(n^2)

class Solution {
public:

    int helper(int m, int n, int i, int j, vector<vector<int>>& dp){
        if(i>=m || j>=n){
            return 0;
        }

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

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

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

        dp[i][j] = right+down;
        return right+down;
    }

    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n,-1));
        return helper(m,n,0,0,dp);
    }

};

• Dynamic Programming:

  Time Complexity : O(n^2)

  Space Complexity : O(n^2)

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));

        dp[0][0] = 1;

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

        for(int i=1; i<m ; i++){
            dp[i][0] = 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] = left+up;
            }
        }

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

Question Link:

https://leetcode.com/problems/unique-paths/description/