jayati

Unique paths

Mar 26th, 2023
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int countpath(int m,int n,int i,int j, vector<vector<int>> &dp)
  4.     {
  5.        
  6.         if(i==m-1 && j==n-1)
  7.         {
  8.             return 1;
  9.         }
  10.         if(i==m || j==n)
  11.         {
  12.             return 0;
  13.         }
  14.         if(dp[i][j]!=0)
  15.         {
  16.             return dp[i][j];
  17.         }
  18.         return dp[i][j] = countpath(m,n,i+1,j,dp)+countpath(m,n,i,j+1,dp);
  19.     }
  20.    
  21.     int uniquePaths(int m, int n) {
  22.         vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
  23.         return countpath(m,n,0,0,dp);
  24.      
  25.     }
  26. };
Advertisement
Add Comment
Please, Sign In to add comment