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];

Show your support

Clapping shows how much you appreciated DeReK’s story.