C++ O(n) Space and O(m*n) Time


  • 1
    B
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<vector<int>> dp(2, vector<int>(n+2, 0));
            dp[0][1] = 1;
            for (int i = 0;i < m;i++) {
                int k = i % 2;
                for (int j = 1;j <= n;j++) {
                    dp[k][j] = max(dp[k][j],dp[k][j-1] + dp[1-k][j]);
                }
            }
            return dp[(m-1)%2][n];
        }
    };

  • 0
    G

    could be more space efficient (although the same big-O complexity)


Log in to reply
 

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