Python：理解阶梯型动态规划解决方案

Question

我一直在研究这个问题。

• 目标是使用砖块建造楼梯
• 有N个砖块，必须全部用于建造楼梯
• 楼梯由严格递增的不同大小的阶梯组成
• 不允许楼梯有相同大小的阶梯
• 每个楼梯至少有两个阶梯，并且每个阶梯都包含至少一个砖块

完整问题链接 http://acm.timus.ru/problem.aspx?num=1017&locale=en

我已经知道这个问题涉及到不同分区和数论/背包问题。目标是给定列表n = [1,2,3,....n -1]，确定存在多少个无序集合加起来等于N。我说无序是因为给定列表没有重复项，所以任何组合可以排序为符合规则的特定回答。我也理解一般的概念是从高度1开始，并添加所有可能的组合，直到新高度用完所有剩余的砖块为止。我意识到有一些模式，比如你已经知道n = 3时存在多少分区，当进入4时，因此使用该数据（动态规划）是解决方案的一部分。

最终我找到了以下解决方案。

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]被分配给上面的条目，因为它已经计算了使用last-1块砖制作所有可能的楼梯的分区总和。

我还知道对角线保存所有分区计数（[3,3] =不同的砖块分区= 3）。我不确定的部分是对角线检查之后数据如何确定（如果left> = last），算法如何知道将该精确矩阵位置添加到当前索引会得到正确的值？这些点处的数据之间的关系是什么？

下面是在10上运行后的2d数组的矩阵，答案为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

- Jeffrey Jarry

Answer 1

这个问题的自底向上解决方案背后的直觉有点难以理解，但是我们来看一下：首先，让我们将m重命名为更加直观的名称：ways。现在，当我们检查这个问题时，我们发现这个问题中有一个有限数量的状态。状态空间由last定义，你可以将其视为你所做的最后一步的砖块数量，left则是你剩余使用的砖块数量。因此，ways[last][left]表示如果你的楼梯最高台阶的高度为last，并且你还有left块砖可用，那么你可以建造的楼梯数量。现在，让我们看看基本情况。ways[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的原因部分是因为我们的基本情况。我们假设用0个砖和0高度制作楼梯有1种方法。然而，根据规则，这并不真正构成“楼梯”，因为楼梯必须有两个或更多的步骤。因此，每个对角线条目都包括一个额外的“无效”楼梯：n个砖块堆叠在一起。

4 bricks
          #
 #        #
 #        #
##        #
13        4

我们需要这个是因为在未来的楼梯中，我们可能会使用堆叠在一起的n块砖头，就像如果我们有9块砖头一样。

9 bricks
  #       #
  #      ##
 ##      ##
 ##      ##
###      ##
135      45

只有n个砖块时，需要减去无效情况。

希望这可以帮到你，祝你好运！

- Peter Wang