如何處理此組合柵欄 - 繪製算法？

我被困在lintcode上的這個問題上，我已經閱讀了兩個過去的解決方案，但是他們都對我沒有意義。如何處理此組合柵欄 - 繪製算法？

的問題是如下：

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.

給定n = 3，K = 2，返回6.

所以我明白的部分是，如果n = 0（我們有0篇）或k = 0（我們有0油漆），我們不能畫什麼那麼返回0

而且如果n == 1，後可以以K的方式畫如此復位K

當n 2，如果相鄰，我們可以用K * 1的方式繪製它如果相鄰職位不同，職位相等，K *（K-1）方式。如果n == 3或更多：相同的相鄰顏色將是：K * 1 * K-1 * 1 * K-1 ... 而且不同的是：K * K-1 * K-1。 ...

我該怎麼辦？我見過一個人再次創建了一個[0，k，2k和0]矩陣，另一個人簡化了「不同顏色」爲（k + k *（k-1））*（k-1）不知道怎麼其中任何跳轉到他們的結論

編輯的那一步：一個傢伙的解決方案如下：

class Solution: 
# @param {int} n non-negative integer, n posts 
# @param {int} k non-negative integer, k colors 
# @return {int} an integer, the total number of ways 
def numWays(self, n, k): 
    # Write your code here 
    table = [0, k, k*k, 0] 

    if n <= 2: 
     return table[n] 

    # recurrence equation 
    # table[posts] = (color - 1) * (table[posts - 1] + table[posts - 2]) 
    for i in range(3, n + 1): 
     table[3] = (k - 1) * (table[1] + table[2]) 
     table[1], table[2] = table[2], table[3] 

    return table[3]

，但我不能瞭解他爲什麼[0]結束他的表格，以及他如何設置遞推方程

來源

2016-12-13 driftdrift

對於沒有相鄰的相同顏色的帖子，您有第一篇文章的k個選項，並且每個附加文章有k-1個，因此k *（k-1）^第（n-1）。對於一次重複，計算放置n-1的方法的數量，然後乘以（n-1）以說明重複的帖子（該帖子被重複），所以k *（k-1）^（ n-2）*（n-1）

總和就是你的答案。

k * (k-1)^(n-1) + k * (k-1)^(n-2) * (n-1)

來源

2016-12-13 20:21:17 Dave

這個問題最困難的部分是設置遞歸。設L是返回給定n個帖子和k個顏色的組合數量的函數。然後有兩種情況需要考慮：

a。添加在相同顏色兩個柱：

L（N + 2中，k）=（K-1）* L（N，K）

灣加入不同顏色的兩個柱：

L（N + 1，K）=（K-1）* L（N，K）

其給出forumula：

L（N，K）=（K-1）×（L（N-1，K）+ L（N-2，k））的

例

對於n = 3和k = 2，假設我們知道前兩個帖子組合的數量是

n = 1 | k = 2

n = 2 | K * K = 4

現在解決對於n = 3，我們需要的是使用具有相鄰的n = 2和n = 3

一個previuosly計算值。不同的顏色：通過添加一個不同於尾部的帖子，sum [2] *（k-1）= 4

b。相同的顏色：回退一個瓷磚，並添加兩個相同的顏色，而不是n = 1，這給出sum [1] *（k-1）= 2

至於矩陣它的味道問題， prev也會很好。

來源

2016-12-13 23:11:38

繼多米尼克G公司的回答，可以給出一個明確的公式 L(n,k)因爲固定ķ它是一個 constant recursive sequence

我的結果是，k >= 2，如果D = sqrt((k+1)^2 - 4)和 u = (k-1+D)/2和v = (k-1-D)/2是這兩種解決方案二次方程x^2 = (k-1)(x + 1)，然後一個具有用於n >= 1

L(n, k) = (k/(k-1))*((u^(n+1)-v^(n+1))/D

如果可以使用足夠的浮點精度進行計算，則會生成一個快速算法。

嗯，恐怕乳膠格式化不起作用，但公式很容易理解

來源

2016-12-14 14:59:48 Gribouillis

如何處理此組合柵欄 - 繪製算法？

回答

相關問題