Skip to content

276 Paint Fence

276. Paint Fence

题目: https://leetcode.com/problems/paint-fence/

难度: Easy

思路:

先解释一下题目意思: fence 栅栏, post 柱子 , no more than two adjacent fence posts have the same color.(一开始看漏,没有看到more than,以为相邻就不能同色)。

本来想画格子找规律,结果走偏了,所以老老实实写递推关系式,貌似是这样的

  • n = 0 : 全为0
  • n = 1 : 有 k种方式
  • n = 2 :有 k * k 种
  • 否则,第n个有两种可能, 跟 n-1 颜色不一样, 跟 n-1 颜色一样, fn = (k-1)fn-1 + (k-1) fn-2

画一下表:对一下递推关系式,正确✅

                n
        0   1   2   3   4
    0   0   0   0   0   0
t   1   0   1   1   0   0
    2   0   2   4   6   10
    3   0   3   9   24  .
    4   0   4   16  60  .

AC 代码

class Solution(object):
    def numWays(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        if n == 0:
            return 0
        else:
            if k == 0: return 0
            elif n == 1: return k 
            elif n == 2 : return k * k
            else:
                dp = [0 for i in range(n+1)]
                dp[0] = 0
                dp[1] = k
                dp[2] = k * k 

                for i in range(3,n+1):
                    dp[i] = (k-1) * dp [i-1] + (k-1) * dp [i-2]
                return dp[-1]



回到顶部