DP with python, O(n) time O(1) space. Straightforward explanation.


  • 0

    This problem is not obvious to me (it is medium in my opinion). I spent quite some time, and came up an idea of dynamic programming approach. Let us use p(n) to denote the color of post n, use w(n) to denote the number of ways to paint post n, and use r(n) to denote the returned number of ways to paint n posts.

    for n == 0, return 0 or 1 # Up to you;
    for n == 1, return k;
    for n == 2,
        if p(2) == p(1), then r(n)=k,
             because the two have the same color.
        if p(2) != p(1), then r(n)=k(k-1)
             because w(1)=k, w(2)=k-1.
    for n >= 3,
        r(n) = r(n,when p(n)==p(n-1)) + r(n,when p(n)!=p(n-1))
    

    When p(n-1) == p(n), we require p(n-2) != p(n-1). This is the same as if we are painting (n-1) posts and the last two posts have different colors, which means same(n)=diff(n−1).

    When p(n-1) != p(n), we have r(n−1) ways to paint the first n-1 posts, and k−1 ways to paint the n-th post. So diff(n)=r(n−1)(k−1).

    Note that r(n−1) is really just the sum of same(n−1) and diff(n−1).

    Code:

    def paintFence(n, k):
        if n == 0:
            return 0
        if n == 1:
            return k
        # Now n >= 2.
        # Initialize same and diff as if n == 2
        same = k
        diff = k*(k-1)
        for i in range(3,n+1):
            r_prev = same + diff  # r(i-1)
            same = diff           # same(i)=diff(i-1)
            diff = r_prev*(k-1)
        return same + diff
    

Log in to reply
 

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