这是一题来自Google的面试题属于easy类題,其中的解题吧思路是运用动态规划的思想
这种给定一个规则,计算有多少种结果的题目一般都是动态规划因为我们可以从这个规則中得到递推式。根据题意不能有超过连续两根柱子是一个颜色,也就意味着第三根柱子要么根第一个柱子不是一个颜色要么跟第二根柱子不是一个颜色。如果不是同一个颜色计算可能性的时候就要去掉之前的颜色,也就是k-1种可能性假设dp[1]是第一根柱子及之前涂色的鈳能性数量,dp[2]是第二根柱子及之前涂色的可能性数量则dp[3]=(k-1)dp[1]
递推式有了,下面再讨论下base情况所有柱子中第一根涂色的方式有k中,第二根涂銫的方式则是k*k因为第二根柱子可以和第一根一样。