276. Paint Fence - cocoder39/coco39_LC GitHub Wiki

276. Paint Fence

Main idea is straightforward. diff[i] is the number of solutions that color of post i is different from that of post i - 1, while same[i] is the number of solutions that color of post i is same as that of post i - 1.

There is a bug in my initialization

same[1] = k; //bug, color of post 1 cannot be same as previous post, there is no previous post at all
diff[1] = k;

However it is same[1] + diff[1] that should be equal to k

int numWays(int n, int k) {
        if (n == 0) return 0;
        vector<int> same(n + 1);
        vector<int> diff(n + 1);
        same[1] = 0;
        diff[1] = k;
        
        for (int i = 2; i <= n; i++) {
            same[i] = diff[i - 1];
            diff[i] = (k - 1) * (diff[i - 1] + same[i - 1]);
        }
        
        return same[n] + diff[n]; 
    }

space complexity is O(n), which can be optimized to O(1) because post i depends only on post (i - 1)

int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0;
        int diff = k;
        
        for (int i = 2; i <= n; i++) {
            int t = same;
            same = diff;
            diff = (k - 1) * (diff+ t);
        }
        
        return same + diff; 
    }
⚠️ **GitHub.com Fallback** ⚠️