An easy to understand explanation of Paint Fence

  • 3

    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.

Log in to reply

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