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