边工作边刷题：70天一遍leetcode: day 85-2

时间：2021-02-15 13:37:41

Paint Fence

要点：

  • 这题是求number of ways，如果是相邻不相同颜色，那么就trivial了：k*(k-1)^(n-1)。所以这里no more than two adjacent fence posts就是不能连续出现3个相同颜色的。
  • 注意这题的解序列都是连续的，所以dp表示的就是以当前fence结束的情况。
  • 这题要用两个dp variables：same：表示最近两个posts是相同颜色，diff：表示最近两个posts是不同color。why？首先这两种情况是exclusive的，所以结果是same+diff。另外由于三个不相连，所以下一个diff是依赖于上一步的same和diff的，而下一步same就是上一步的diff。这样就有了递推式了。
  • 为什么要分开而不能只优化dp[i]？dp[i-2]/dp[i-1]的情况是不明的，没法确定当前的颜色。
  • 以前还见过道min cost的题，这题只是相邻的不同色。因为每种颜色的cost的非对称性，dp需要记录每种颜色上一步的min cost，从而再得到下一步。同样，因为结果是连续的，所以最后就是几种颜色中最小的那个 http://pastebin.com/PS4RPzLY

https://repl.it/CfFI/1

错误点：

  • xrange(2, n) or xrange(3, n+1)都可以
  • python的same, diff可以同时更新，右边的全是old值，没有更新顺序依赖
# There is a fence with n posts, each post can be painted with one of the k colors.

# You have to paint all the posts such that no more than two adjacent fence posts have the same color.

# Return the total number of ways you can paint the fence.

# Note:

# n and k are non-negative integers.

# Hide Company Tags Google

# Hide Tags Dynamic Programming

# Hide Similar Problems (E) House Robber (M) House Robber II (M) Paint House (H) Paint House II

class Solution(object):

    def numWays(self, n, k):

        """

        :type n: int

        :type k: int

        :rtype: int

        """

        if n==0 or k==0: return 0

        if n==1: return k

        same, diff = k, k*(k-1)

        for i in xrange(2, n): # error: not 3 but 2

            same, diff = diff, same*(k-1)+diff*(k-1)

        return same+diff

sol = Solution()

assert sol.numWays(3, 2)==6

assert sol.numWays(3, 1)==0

assert sol.numWays(2, 2)==4

相关文章