Leetcode 276: Paint Fence

https://leetcode.com › problems › paint-fence

Notes:

A nice dp problem.

Let us start with some small number:

at n = 1, there are k ways;

now move on the the second one. If we choose to the same color as before, then there are a = k ways (with the last two having the same colors); if we choose a different color, then there are b = k*(k-1) (with the last two having different colors).

now is the key: let's move on the 3rd one.

If we are at the first case with the last two having the same color, then we have to choose a different color, which gives a*(k-1) ways, now it becomes the case with the last two elements having different colors;

if we are at the second case with the last two having different colors. we have two choices:

1): choose a color which is the same as the last one, and there are b ways to do this; and now it becomes the case with the last two elements with the same color;

2): choose a different color from that of the last element, and there are b*(k-1) ways to do this. After this, it is still the same case as before;

so we can derive the formula as the following:

a is the ways with the last two having the same color;
b is the ways with the last two having different colors.

So for the first place, a = 0, b = k; then

t = b;//save b;
b = (b + a) * (k-1)
a = b;

So this question can be easily to modify to ask: how about at most 3 (or n) adjacent fences having the same color?

See the code below:

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k;
        for (int i = 2; i <= n; ++i) {
            int t = diff;
            diff = (same + diff) * (k - 1);
            same = t;
        }
        return same + diff;
    }
};