c++ Dynamic Programming


  • 0
    W
    int uniquePaths(int m, int n) {
        if (m < 0 || n < 0)
            return 0;
        int paths = 0;
        vector<vector<int> > ps;   
        vector<int> vi(n+1, -1);
        for (int i = 0; i <= m; ++i) {
            ps.push_back(vi);
        }
        
        paths = UniqPaths(m, n, ps);
        return paths;
    }  
    
    int UniqPaths(int m, int n, vector<vector<int> > &ps) {
        int paths = 0; 
        if ((1 == m && 1 == n) || (2 == m && 1 == n) || (1 == m && 2 == n))
            return 1;
        
        if (m > 1) {
            if (ps[m-1][n] > 0)
                paths += ps[m-1][n];
            else
                paths += UniqPaths(m-1, n, ps);
        }
        
        if (n > 1) {
            if (ps[m][n-1] > 0)
                paths += ps[m][n-1];
            else
                paths += UniqPaths(m, n-1, ps);            
        }
        
        ps[m][n] = paths;
        return paths;
    }

Log in to reply
 

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