# Dynamic programming, C++, O(n) time, O(1) space, 0ms

• 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;
}
};``````

• I don't understand why we need to calculate solutions when last two fences have the same color? Why dp1[n-1] + dp2[n-1] is the final result? Can anybody explain it a little bit?

• Great code and explanation! I rewrite it a little bit: `s` means same and stands for the last element of your `dp1`; `d` means different, `d1` and `d2` stands for the last two elements of your `dp2`.

In each loop, `dp1[i] = dp2[i - 1]` turns into `s = d2` and `dp2[i] = (k - 1) * (dp2[i - 2] + dp2[i - 1])` becomes `d2 = (k - 1) * (d1 + d2)`. Moreover, `d1` needs to be set to the old `d2`, which is recorded in `s`. So we have `d1 = s`.

Finally, the return value `dp1[n - 1] + dp2[n - 1]` is just `s + d2`.

The code is as follows.

``````class Solution {
public:
int numWays(int n, int k) {
if (n < 2 || !k) return n * k;
int s = k, d1 = k, d2 = k * (k - 1);
for (int i = 2; i < n; i++) {
s = d2;
d2 = (k - 1) * (d1 + d2);
d1 = s;
}
return s + d2;
}
};``````

• Thanks for your improvement, it really makes the solution more clear for others to understand, great job!!

• why you say "when the color of last two fences (whose indexes are i-1,i-2) are same", why it's not i and i - 1 are the last two fences?

• Great stuff. I don't feel this is an easy problem however...

• actually, if you know how DP works, it's a easy level. But if you are like me who are just DP beginners, it is hard to figure out the formula, lol

• Why need two-dimensional array?
Can we use one-dimensional array instead?

``````1. Same color for n-1 and n :　dp[n] = dp[n-2] *(k-1)
2. Different color for n-1 and n : dp[n] = dp[n-1] * (k-1)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.