動態規劃 - 建設方式的數量

Question

我試圖用動態規劃解決以下問題 - 我似乎無法找到重現。問題是如下：

「建築物是由堆積的至少兩個塊形成的結構

你的任務是找到總的方式，使得所有塊在提高建築物使用

。

例如，對於n = 5，答案是2，因爲[5]，[2,3]

對於n = 6，答案是4，因爲[6]，[2,4]，[ 2，2]，[3，3]「

有人可以幫助我瞭解如何從底部向上或頂部進行此操作n的方式？

Answer 1

這與partition problem具有相同的想法。假設f[i][j]減去非減小大小的塊中的i的分區數，使得最後的塊大小爲j。您更新規則，那麼，會是：

f[i+k][k] += f[i][j], for k>= max(2, j) // bottom-up approach 

和分區數的答案：

f[n][2] + f[n][3] + ... + f[n][n] 

或者，你可以使用自上而下的方法：

f[i][j] += f[i-k][k] for 2 <= k <= j 

運行這對你的例子有：

Initialize f[i][i] = 1, i >= 2 and the rest set to 0 

f[2][2] = 1 

f[3][2] = f[1][2] = 0 
f[3][3] = 1 

f[4][2] = f[2][2] = 1 
f[4][3] = f[1][2] + f[1][3] = 0 
f[4][4] = 1 

f[5][2] = f[3][2] = 0 
f[5][3] = f[2][2] + f[2][3] = 1 
f[5][4] = f[1][2] + f[1][3] + f[1][4] = 0 
f[5][5] = 1 


f[6][2] = f[4][2] = 1 
f[6][3] = f[3][2] + f[3][3] = 1 
f[6][4] = f[2][2] + f[2][3] + f[2][4] = 1 
f[6][5] = f[1][2] + f[1][3] + f[1][4] + f[1][5] = 0 
f[6][6] = 1 

count(5) = f[5][2] + f[5][3] + f[5][4] + f[5][5] = 2 
count(6) = f[6][2] + f[6][3] + f[6][4] + f[6][5] + f[6][6] = 4 

Answer 2

實際上有一個非常簡單的解決方案：包含1的n的分區數等於分區總數(n - 1)。想一想的一種方法是想象從包含一個n的每個分區中刪除一個1;不包含1的n的任何分區不能以這種方式進行轉換。

因此，我們可以簡單地從經典partition recurrence，p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...刪除第一項，並從中獲得：

p_without_1s(k) = p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ... 

或者

p_without_1s(k) = p(k) - p(k - 1)