# C++ O(n) dp solution with thorough explanation.

• ``````class Solution {
public:
int numWays(int n, int k) {
/*
dp[i][0] = nr of ways to paint fences 0 to i, when fence i and fence (i-1) have not the same colour.
dp[i][1] = nr of ways to paint fences 0 to i, when fence i and fence (i-1) have the same colour.
*/
if(n == 0)
return 0;
if(n <= 2)
return int(pow(k,n));   // n = 1 => ways = k, n = 2 => ways = k * k
vector<vector<int> >dp(n, vector<int>(2,0));
// base cases
dp[0][0] = dp[0][1] = k;
dp[1][0] = k*(k-1);
dp[1][1] = k; // when fence 0 and fence 1 have the same colour, then possible colours are cc, where 1<=c<=k.
for(int i=2; i<n; ++i){
// if fence i and i-1 should not have same colour, then fence i has only k-1 possible colours.
dp[i][0] = (k-1) * (dp[i-1][0] + dp[i-1][1]);
// if fence i and i-1 have same colour, then fence i-2 should not have the same colour, and this is captured by
// dp[i-1][0].
dp[i][1] = dp[i-1][0];
}
// final result is by painting fences 0 to n-1, with fence n and n-1 having the same colour or not.
return dp[n-1][0] + dp[n-1][1];

}
};
``````

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