# 514. Paint Fence

这道题会了不难难了不会。有一句话价值100万：The 3rd cannot be the same with both 1 and 2, so it either different from 2nd or 1st

int[] dp = new int[n+3]; //n+3 just for enough room when n is small

dp[0] = 0;

dp[1] = k;

dp[2] = k*k;

if(n< 3){

return dp[n];

}

//3rd cannot be the same with both 1 and 2, so it either different from 2nd or 1st

for(int i=3; i<=n; i++){

dp[i] = (k-1)*(dp[i-1]+dp[i-2]);

}

return dp[n];