There are already some good analysis about this problem in the forum. However, maybe my own way of analyzing this problem can also help.
For a fence, there are only two cases: either it's the same color with the previous fence, or different color with the previous fence. Hence we can create an array of n*2, in which n represents the total number of fences and the column is 2 for two states (same color or different color). We give this array the name "dp".
Now what's the meaning of dp[i]? In detail, it means that if we have in total i fences, the number of ways to paint when ith fence has the same color as the i-1 fence. Similarly, dp[i] means the number of ways to paint when ith fence has the different color as the i-1 fence. The total ways to paint the in total i fences equals dp[i] + dp[i].
With this in mind, we have the following equation:
dp[i] = dp[i-1]
Translation of the above equation: the count of possibilities when ith fence has the same color as the i-1 fence equals count of possibilities when i-1 th fence has a different color with the i-2 th fence. Because:
--1. The i-1 th fence cannot have the same color as i-2 fence, otherwise there will be 3 colors adjacent. That's why we only have one item : dp[i-1] in which the second bracket contains "1" or to say, "different" state.
--2. Now we are just adding the same color at ith fence using i-1's fence color.
Following this logic we would also have:
dp[i] = dp[i-1]*(k-1) + dp[i-1]*(k-1)
Notice that there are two items on the right of the equation. Reason is that when i fence has different color with i-1 fence. We can include cases where i-1 and i-2 fence color to be either same or different.
Below is the python code:
class Solution(object): def numWays(self, n, k): """ :type n: int :type k: int :rtype: int """ if n<=0: return 0 if n == 1: return k dp = [[0,0] for _ in range(n)] dp = [0, k] # tricky part. Imagine that there is a virtual extra fence on the left. # dp[i] means at i fence, it's same color with the i-1 fence. At this case how many possibilities. for i in range(1, n): dp[i] = dp[i-1] dp[i] = dp[i-1]*(k-1) + dp[i-1]*(k-1) return sum(dp[-1])
The disadvantage of this approach maybe that I may use more memories(O(n)) than some of other solutions(O(1)). But I intentionally sacrifice the memory for explaining the questions clearer since I consider a matrix would give us better image of what's going on.