动态规划 - 制作建筑物的方式数量

Question

我正在尝试使用动态规划解决以下问题-我似乎找不到递归。问题如下：

“建筑是由至少两个方块组成的结构。

您的任务是找到所有用于制造建筑物的方块的总方法。

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

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

有人能帮我理解如何从自底向上或自顶向下的方式进行吗？

- user2871354

---

“n” 应该代表什么意思？ - sve

n是块数。 - user2871354

(1) 动态规划有助于找到最优解，而不是扩展所有可能性。 (2) 为什么不是5个组合，而是7个组合：[5]、[1,4]、[1,1,3]、[1,1,1,2]、[1,1,1,1,1]、[2,3]、[2,1,2]？这与“建筑物是由柱子和梁构成的结构”有什么关系？ - Ken Cheung

@KenCheung 最小尺寸必须为2（而不是1） - BobbyTables

虽然不完全相同，但这与整数划分问题非常相似。https://en.wikipedia.org/wiki/Partition_(number_theory) 可以提供一些见解。 - moreON

Answer 1

这个问题与 划分问题 的思路相同。设 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

- sve

Answer 2

其实这个问题有一个非常简单的解决方案：包含 1 的 n 的分区数等于 (n - 1) 的总分区数。一种思考方式是想象从每个包含 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)

- גלעד ברקן