# An easy to understand explanation of Paint Fence

• 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][0]? 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][1] 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][0] + dp[i][1].

With this in mind, we have the following equation:

``````dp[i][0] = dp[i-1][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][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][1] = dp[i-1][1]*(k-1) + dp[i-1][0]*(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] = [0, k]  # tricky part. Imagine that there is a virtual extra fence on the left.

# dp[i][0] 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][0] = dp[i-1][1]
dp[i][1] = dp[i-1][1]*(k-1) + dp[i-1][0]*(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.

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