I use window `[a, b, c]`

, initialized to `[0, k, k*k]`

, the answers for n=0, 1 and 2. Shift it `n`

steps and then return `a`

. Takes O(n) time and O(1) space.

Using a window of **three** elements rather than the usual two elements allows me to handle the case n=0 without special case code (the `if (n==0) return 0;`

you can see in almost every solution). And shifting a two-element window is usually done with a temporary third variable anyway. I just make that third variable more valuable.

```
int numWays(int n, int k) {
int a = 0, b = k, c = k*k;
while (n--) {
a = b;
b = c;
c = (a + b) * (k - 1);
}
return a;
}
```

For an explanation of the computation, look for example here.