```
class Solution {
public:
int numWays(int n, int k) {
int* Tsame = new int[n];
int* Tdiff = new int[n];
std::fill_n(Tsame, n, -1);
std::fill_n(Tdiff, n, -1);
Tsame[0] = 0;
Tdiff[0] = k;
Tsame[1] = k;
Tdiff[1] = k * (k - 1);
for(int i = 0; i < n; ++i){
if(-1 == Tsame[i]){
Tsame[i] = Tdiff[i - 1];
}
if(-1 == Tdiff[i]){
Tdiff[i] = Tsame[i - 1] * (k - 1) + Tdiff[i - 1] * (k - 1);
}
}
return Tsame[n - 1] + Tdiff[n - 1];
}
};
```