Python solution with detailed explanation


  • 1
    G

    Solution

    Paint Fence https://leetcode.com/problems/paint-fence/?tab=Description

    Memoization

    • The recursion tree is shown here: https://goo.gl/photos/ujNNfVvcphpBhKgXA
    • Standard backtracking - use so_far to track the path and use it to pick the next candidates such that no three houses are painted same.
    • Throw in a cache to get memoization done
    • Improve it - you do not need entire path but just last two.
    from collections import defaultdict
    class Solution(object):
        def ways(self, i, n, k, so_far, cache):
            if len(so_far) == n:
                return 1
            else:
                is_same = len(so_far)>=2 and so_far[-1] == so_far[-2]
                if i in cache and is_same in cache[i]:
                    return cache[i][is_same]            
                cache[i][is_same] = 0
                for j in range(k):
                    if is_same and so_far[-1] == j:
                        continue
                    so_far.append(j)
                    cache[i][is_same] += self.ways(i+1, n, k, so_far, cache)
                    so_far.pop()
                return cache[i][is_same]
            
        def numWays(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: int
            """
            # https://goo.gl/photos/ujNNfVvcphpBhKgXA
            if n == 0 or k == 0:
                return 0
            cache = defaultdict(dict)
            return self.ways(0, n, k, [], cache)
    

    https://discuss.leetcode.com/topic/30569/explanation-of-dp-o-n-time-complexity-o-1-space-complexity/3

    Dynamic Programming

    class Solution(object):
        def numWays(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: int
            """
            if k == 0 or n == 0:
                return 0
            if n == 1:
                return k
            ways, fdiff = k*k, (k*k)-k
            for i in range(3, n+1):
                x = (k-1)*ways + fdiff
                fdiff = (k-1)*ways
                ways = x
            return ways
    

Log in to reply
 

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