algorithm - 动态规划 - build 建筑物的方法数

Question

我正在尝试使用动态规划解决以下类型的问题 - 我似乎无法找到重复出现的问题。问题如下:

“建筑物是由至少两个积木堆砌而成的结构。

你的任务是找到所有的方法，使得所有的方 block 都被用来建​​造建筑物。

例如，对于 n = 5，答案是 2，因为 [5] , [2 , 3] 。

对于 n = 6，答案是 4 因为 [6] , [2 , 4] , [2 ,2 ,2] , [3 ,3]"

谁能帮我理解如何从下往上或自上而下的方式做到这一点？

Answer 1

这与 partition problem 有相同的想法.让 f[i][j] 取消非递减大小块中 i 的分区数，使得最后一个 block 大小为 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