C++ 0ms with and without DP


  • 0
    1

    The problem can be solved without dp using the formula (m+n-2)!/(m-1)!(n-1)!

    int uniquePaths(int m, int n) {
    long int ans=1;
    for(long int i=m;i<=(m+n-2);i++)
    {
    ans=i;
    ans/=i-m+1;
    }
    return ans;
    }
    

    Using dynamic programming,at every cell (i,j),it can come from top or left
    Hence the equation is dp[i][j]=dp[i-1[j]+dp[i][j-1]

    int uniquePaths(int m, int n) {
    //There is only 1 way to reach any cell on 0th row or 0th column.initialize all to 1
    vector<vector<int> > dp(m,vector<int>(n,1));
    for(int i=1;i<m;i++)
    {
    for(int j=1;j<n;j++)
    {
    dp[i][j]=dp[i-1][j]+dp[i][j-1];//from top or from left
    }
    }
    return dp[m-1][n-1]; }```

  • 0
    A

    @vk1993 Your definitely haven't tried the combinatorics method.


Log in to reply
 

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