Jef*_*rry 3 python algorithm dynamic-programming number-theory
我一直在研究这个问题。
完整问题的链接http://acm.timus.ru/problem.aspx?num=1017&locale=en
我已经知道这是处理不同的分区和数论/背包问题。目标是有效地给出一个列表 n = [1,2,3,....n -1] 确定存在多少个加起来为 N 的无序集合。我说无序是因为给定的列表没有重复项，因此任何组合都可以排序为给定大小的有效特定答案以符合规则。我也理解一般概念是你从高度 1 开始并分支/添加所有可能的组合，直到新的高度超过砖块，并且仅当新高度用完所有剩余的砖块时才添加到总组合中那一点。我意识到有一些模式，就像您在进入 4 时已经知道 n = 3 存在多少个分区一样，因此使用该数据（动态编程）是解决方案的一部分。
我最终找到了以下解决方案。
n = int(input())
m = [[0 for i in range(n + 1)] for j in range(n + 1)]
m[0][0] = 1 # base case
for last in range(1, n + 1):
for left in range(0, n + 1):
m[last][left] = m[last - 1][left]
if left >= last:
m[last][left] += m[last - 1][left - last]
print(m[n][n] - 1)
所以我明白最后一个变量代表它正在使用多少块砖。左边的循环让它运行并传输缓存的数据。所以我理解 m[last][left] 被分配给上一个条目，因为它已经具有使用最后 - 1 块砖块计算出的所有可能楼梯的分区总和。
我还知道对角线包含所有分区计数（[3,3] = 砖的不同分区= 3）我不确定的部分是对角线检查后确定数据的方式（如果左>=最后） ，算法如何知道将确切的矩阵位置添加到当前索引会得到正确的值？这些点的数据之间有什么关系？
下面是运行 10 后的二维数组的矩阵，其中答案是 9
=0 1 2 3 4 5 6 7 8 9 10
0 |1 0 0 0 0 0 0 0 0 0 0
1 |1 1 0 0 0 0 0 0 0 0 0
2 |1 1 1 1 0 0 0 0 0 0 0
3 |1 1 1 2 1 1 1 0 0 0 0
4 |1 1 1 2 2 2 2 2 1 1 1
5 |1 1 1 2 2 3 3 3 3 3 3
6 |1 1 1 2 2 3 4 4 4 5 5
7 |1 1 1 2 2 3 4 5 5 6 7
8 |1 1 1 2 2 3 4 5 6 7 8
9 |1 1 1 2 2 3 4 5 6 8 9
10 |1 1 1 2 2 3 4 5 6 8 10
这个问题的自下而上解决方案背后的直觉有点难以理解，但这里是：
首先，让我们重命名m为更直观的名称：ways。现在，当我们检查这个问题时，我们发现这个问题的状态数量是有限的。状态空间由 和 定义last，您可以将其视为上一步中制作的砖块数量，以及left，即您剩余使用的砖块数量。
因此，如果楼梯的最高台阶高度为，并且您有砖块可以ways[last][left]使用，则 表示您可以建造的楼梯数量。lastleft
现在，让我们看看基本情况。ways[0][0]告诉我们如果台阶高度为 0 并且剩下 0 块砖，我们可以建造多少个楼梯。好吧，只有一种方法可以做到这一点：放下 0 块砖！最后，ways[0][0] = 1。如果你看一下ways[0][1]，就会问：如果最后一步的高度为 0 并且我们还剩下 1 块砖，我们可以用多少种方式建造楼梯？这是不可能的，因为从左到右的台阶高度必须严格增加。正如你所看到的，ways[0][1], ways[0][2], ... , ways[0][k], k > 0一切都将为零。
自下而上解决方案中最困难的部分是重复。让我们看看嵌套 for 循环内的第一行。
ways[last][left] = ways[last - 1][left]
这就是说，我们用最后一步高度last和left剩余砖块可以制作的楼梯数量等于我们用最后一步高度last-1和left剩余砖块可以制作的楼梯数量。这应该是有道理的，因为如果你有一个更高的最后一步，它的限制就会减少，并ways[last][left]成为的超集ways[last-1][left]。可以这样想：我们有 5 块砖块可供使用。我们保证能够制作多少个楼梯？与我们用 4 块砖拼出的数字相同。至少，你可以简单地将额外的砖块添加到右侧最高的台阶上，它仍然有效。
4 bricks 5 bricks
#
# #
# #
## ##
13 14
当您剩余的砖块数量大于或等于您上一关的砖块数量时会发生什么？在这种情况下，我们可以在现有台阶的左侧建造一个新楼梯。但这个新楼梯不能比last-1砖块高，因为同样，台阶必须严格增加。那么那是多少级楼梯呢？好吧，我们正在使用last砖块来制作台阶，因此我们还left-last剩下砖块来建造左侧的楼梯。这个号码就在牢房里ways[last-1][left-last]。幸运的是，我们之前已经计算过该值，因此这只是一个简单的查找。
一个示例可能有助于了解实际数字，因此我将进行 的计算n=2。
# initial state with the base case
[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
# ways[1][0] = ways[0][0] at least b/c the spare brick can go on highest step
[1, 0, 0]
[1, 0, 0]
[0, 0, 0]
# ways[1][1] = ways[0][1] by the same logic
# ways[1][1] += ways[0][0] because we use up 1 brick making the step,
# and we have 0 bricks left, and we need the max height to be 0
[1, 0, 0]
[1, 1, 0]
[0, 0, 0]
# ways[1][2] = ways[0][2] by the same logic
# ways[1][2] += ways[0][1] because we use up 1 brick making the step,
# and we have 1 bricks left, and we need the max height to be 0 (impossible!)
[1, 0, 0]
[1, 1, 0]
[0, 0, 0]
# ways[2][0] = ways[1][0] by the same logic
[1, 0, 0]
[1, 1, 0]
[1, 0, 0]
# ways[2][1] = ways[1][1] by the same logic
# ways[2][1] += ways[1][0] because we use up 1 brick making the step,
# and we have 0 bricks left, and we need the max height to be 0
[1, 0, 0]
[1, 1, 0]
[1, 1, 0]
# ways[2][2] = ways[1][2] by the same logic
# ways[2][2] += ways[1][0] because we use up 2 bricks making the step,
# and we have 0 bricks left, and we need the max height to be 1.
# That's perfect, because we can make a step of max height 1 with 0 steps
[1, 0, 0]
[1, 1, 0]
[1, 1, 1]
这就是填写表格背后的逻辑ways。这是代码的最后一行：
print(ways[n][n] - 1)
我们需要减去 1 的部分原因是我们的基本情况。我们假设有 1 种方法可以用 0 块砖和 0 高度制作楼梯。然而，根据规则，这并不真正构成“楼梯”，因为楼梯必须有两个或更多台阶。因此，每个对角线入口都包含一个额外的“无效”楼梯：n 块相互堆叠的砖块。
4 bricks
#
# #
# #
## #
13 4
我们需要这个，因为在未来的楼梯中，我们可以使用n相互堆叠的砖块，就像我们有 9 块砖块一样。
9 bricks
# #
# ##
## ##
## ##
### ##
135 45
只是当你只有n砖块时，你需要减去那个无效的情况。
我希望这有帮助——祝你好运！
| 归档时间： |
|
| 查看次数： |
2174 次 |
| 最近记录： |