Given an 'n', there are two kinds of color combinations.

- The last two colors are the
**same**, which is denoted as**fsame**in my code. - The last two colors are
**different**, which is denoted as**fdiff**in my code.

Now consider 'n+1' and its two kinds of solutions.

- Regarding case 1, the new fsame equals the old fdiff, right? Otherwise, there would be three adjacent walls with the same color.
- Regarding case 2, all old combinations with length 'n' are legally combined with one of remaining (k-1) colors.

So the update formula is

- fsame(n + 1) = fdiff(n)
- fdiff(n + 1) = (fsame(n) + fdiff(n)) * (k - 1)

As no need to keep all history of fsame and fdiff, so the space complexity is O(1). The code is as follows.

```
class Solution {
public:
int numWays(int n, int k) {
if (n == 0) {
return 0;
}
if (n == 1) {
return k;
}
if (n == 2) {
return k * k;
}
// fsame(n): the number of combs, whose last digits are the same.
// fdiff(n): the number of combs, whose last digits are different.
int fsame = k, fdiff = k * (k - 1);
for (int p = 3; p <= n; ++p) {
auto fsame1 = fdiff;
auto fdiff1 = (fsame + fdiff) * (k - 1);
fsame = fsame1;
fdiff = fdiff1;
}
return fsame + fdiff;
}
};
```

Tian Xia