Easy recursive DP


  • 0
    P
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<vector<int>>dp(m + 1,vector<int>(n + 1, 1));
            return rec(m,n,dp);
        }
        int rec(int m, int n, vector<vector<int>>&dp)
        {
            if(dp[m][n] != 1) return dp[m][n];
            if (m==1)return 1;
            if(n == 1)return 1;
            //if(m < 0 || n < 0) return 0;
            return (dp[m -1 ][n] = rec(m - 1,n ,dp)) + (dp[m][n -1] =rec(m ,n - 1,dp));
        }
    };
    

    In my opinion it is easier to write recursive DP rather than iterative.
    Just come up with the recurrence and write the recurrence as code. 2 base cases and one equation. It is also tail recursive (I think). It should not take more stack space for each function.


Log in to reply
 

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