C++, O(m+n) space complexity.


  • 0
    C
    /**
     * Time complexity: O(m*n)
     * Space complexity: O(m+n)
     * 
     * This method is an optimized version of simple dynamic programing solution from space O(m*n) to O(m+n).
     * 
     * By observing the order of calculation in simple dynamic programming:
     * 
     * for(int i = 0; i < m; i++) {
         for(int j = 0; j < n; j++) {
             ...
         }
     }
     * We can find that every row is used exactly once, and in order.
     * Therefore allocating a row of memorizing array is enough. 
     */
    int uniquePaths(int m, int n) {
        // ensure m > n to save space since we are going to allocate an array of size n.
        if(n < m)   return uniquePaths(n, m);
        
        vector<int> dp(n, 1); 
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                dp[j] += dp[j-1];
            }
        }
        
        return dp[n-1];
        
    }

Log in to reply
 

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