dp[n] = dp[n - 1] * k - dp[n - 3] * (k - 1)

```
class Solution {
public:
int numWays(int n, int k) {
vector<int> ans{k, k * k, k * k * k - k};
if(n == 0) return 0;
if(n <= 3) return ans[n - 1];
for(int i = 3; i < n; i++) {
int tmp = ans[2];
ans[2] = ans[2] * k - ans[0] * (k - 1);
ans[0] = ans[1];
ans[1] = tmp;
}
return ans[2];
}
};
```