Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
645 B
0
Indexable
Never
class Solution {
public:
    int solve(int i,int j,int m,int n,vector<vector<int>>&dp){
        if(i==m-1 && j==n-1) return 1;

        int r=0,d=0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(j<n-1) r=solve(i,j+1,m,n,dp);
        if(i<m-1) d=solve(i+1,j,m,n,dp);
        return dp[i][j]=d+r;
        //return 0;
    }

    int uniquePaths(int m, int n) {
        //int ans=0;
        vector<vector<int>>dp(m+1,vector<int>(n+1,1));    
        dp[m-1][n-1]=1;

        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }
};
Leave a Comment