Need two one-dimensional array dp1 and dp2,

dp1[i] means the number of solutions when the color of last two fences (whose indexes are i-1,i-2) are same.

dp2[i] means the number of solutions when the color of last two fences are different.

So

**dp1[i]=dp2[i-1],**

* dp2[i]=(k-1)(dp1[i-1]+dp2[i-1]) =(k-1)*(dp2[i-2]+dp2[i-1])**

Final result is dp1[n-1]+dp2[n-1];

In the code, variable *a,c* mean the last two items of dp1, variable *b,d* mean the last two items of dp2, and c could be eliminated.

```
class Solution {
public:
int numWays(int n, int k) {
if(n<=1 || k==0)return n*k;
int a=k,b=k*(k-1),c=0,d=0;
for(int i=2;i<n;++i){
d=(k-1)*(a+b);
a=b;b=d;
}
return a+b;
}
};
```