O(N**2) space and O(n) space dp solutions (C++)


#1
int solutionDPLinearSpace(int A, int B)
{
    vector<int> prev(B), cur(B);
    for (int i = 0; i < B; ++i)
        prev[i] = 1;
    for (int i = 1; i < A; ++i) {
        for (int j = 0; j < B; ++j) {
            if (j == 0)
                cur[j] = 1;
            else
                cur[j] = cur[j - 1] + prev[j];
        }
        swap(prev, cur);
    }
    
    return prev[B - 1];
}

int solutionDP(int A, int B)
{
    vector<vector<int>> dp(A, vector<int>(B));
    for (int i = 0; i < B; ++i)
        dp[0][i] = 1;
    for (int i = 0; i < A; ++i)
        dp[i][0] = 1;
    for (int i = 1; i < A; ++i) {
        for (int j = 1; j < B; ++j) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        }
    }
    
    return dp[A - 1][B - 1];
}

int Solution::uniquePaths(int A, int B) {

    return solutionDPLinearSpace(A, B);
}