C++ DP 5ms.. O(mn)


  • -1
    H
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<vector<int> > opt(m+1 , vector<int>(n+1,0));
    
            opt[0][1] = 1;
            
            for(int i = 1 ; i < m+1 ; i++){
                for(int j =1 ; j<n+1 ; j++){
                    opt[i][j] = opt[i-1][j] + opt[i][j-1] ;
                }
            }
            
            return opt[m][n];
        }
    };
    

    opt[0][1] = 1 because for first path 0+1 = 1 paths are there...
    using optimal substructure.


Log in to reply
 

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