C++ DP O(n) space solution with only one 1D array


  • 1
    J

    Many space-optimized DP solutions use 2 arrays, but can do even better by using just one.

    int uniquePaths(int m, int n) {
        //table[j]: number of paths from board[0][0] to boad[i][j], i < m; j < n;
        vector<int> table(n, 1);
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                table[j] += table[j-1];
    
        return table[n-1];
    }

  • 0
    D

    why our code only beats 7% of cpp code?


Log in to reply
 

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