Leetcode 276: Paint Fence (O(n^2) space)

leetcode_276a.cpp

#include <iostream>
#include <vector>

using namespace std;

int numWays(int n, int k) {
    if (n==0 || k==0) return 0;
    vector<vector<int>> dp(k, vector<int>(n,1));

    for (int c=1; c<n; ++c) {
        for (int r=0; r<k; ++r) {
            int sumPrevCol = 0;
            for (int i=0; i<k; ++i) sumPrevCol += dp[i][c-1];
            dp[r][c] = sumPrevCol - (c<2 ? 0 : dp[r][c-2]);
        }
    }
    int res = 0;
    for (int r=0; r<k; ++r) res += dp[r][n-1];
    return res;
}

int main() {
    cout << numWays(3, 2) << "\n";
    return 0;
}