python : Stairstep DP solution understanding

Question

我一直在看这个问题。

• 目标是用砖 block 搭建楼梯
• 有N block 砖，必须全部用来搭楼梯
• 楼梯由大小不一的台阶组成，按严格递增的顺序排列
• 楼梯不允许有相同大小的台阶
• 每个楼梯至少由两级组成，每级至少包含一 block 砖

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

我已经知道这是处理不同的分区和数论/背包问题。目标是有效地给出一个列表 n = [1,2,3,....n -1] 确定存在多少个加起来为 N 的无序集。我说无序是因为给定列表没有重复项，因此任何组合都可以作为给定大小的有效特定答案进行排序以符合规则。我也理解一般概念是你从高度 1 开始并分支/添加所有可能的组合，直到新高度超过砖 block 并且只有在新高度用完所有剩余砖 block 时才添加到总组合中那一点。我意识到有一些模式，比如当进入 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)

所以我明白最后一个变量代表它使用了多少 block 砖。左边的循环让它运行并传输缓存的数据。所以我理解 m[last][left] 被分配给上一个条目，因为它已经计算出所有可能使用 last - 1 block 的楼梯的分区总和。

我还知道对角线包含所有分区计数([3,3] = 不同的砖 block 分区 = 3)我不确定的部分是在对角线检查后确定数据的方式(如果 left >= last)，算法如何知道将确切的矩阵位置添加到当前索引会得到正确的值？这些点的数据之间有什么关系。

下面是二维数组在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

Answer 1

这个问题的自下而上解决方案背后的直觉有点难以理解，但这里是:

首先，让我们将 m 重命名为更直观的名称:ways。现在，当我们检查这个问题时，我们看到这个问题中的状态数量是有限的。状态空间由 last 定义，您可以将其视为您完成的最后一步中的砖 block 数量，以及left，这是您剩余要使用的积木数量。

因此，ways[last][left] 表示如果楼梯的最高台阶的高度为 last，并且您有 left 要使用的积木。

现在，让我们看看基本情况。 ways[0][0] 告诉我们如果我们有一个高度为 0 的台阶并且还剩下 0 个砖 block ，我们可以 build 多少个楼梯。好吧，只有一种方法可以做到:放下 0 block 积木!因此，ways[0][0] = 1。如果您查看 ways[0][1]，这会问:如果最后一步的高度为 0 且我们还剩下 1 block 砖，我们可以用多少种方式 build 楼梯？这是不可能的，因为从左到右的台阶高度必须严格递增。如您所见，ways[0][1], ways[0][2], ... , ways[0][k], k > 0 都将为零。

自下而上解决方案中最困难的部分是重复。让我们看一下嵌套 for 循环中的第一行。

ways[last][left] = ways[last - 1][left]

这表示我们可以使用高度 last 和剩余的 left 积木的最后一步制作的楼梯数量等于我们可以使用 a 制作的楼梯数量last-1 高度的最后一步，剩余 left 砖 block 。这应该是有道理的，因为如果你有一个更高的最后一步，它就会变得更少限制，并且 ways[last][left] 成为 ways[ 的 superset last-1][左]。可以这样想:我们有 5 block 积木可以使用。我们保证能做多少个楼梯？与我们用 4 block 积木可以拼出的数字相同。至少，您可以简单地将额外的砖 block 添加到右侧最高的台阶上，它仍然有效。

4 bricks                           5 bricks
                                       #
   #                                   #
   #                                   #
  ##                                  ##
  13                                  14

当您剩下的积木数量大于或等于您上一关的积木数量时会发生什么？在这种情况下，我们可以在现有台阶的左侧 build 一个新楼梯。但是这个新楼梯不能比 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 block 砖和 0 高度制作楼梯。但是，按照规则，这并不能真正构成“楼梯”，因为楼梯必须有两个或更多的台阶。因此，每个对角线条目都包含一个额外的“无效”楼梯:n 个砖 block 堆叠在一起。

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

我们需要这个，因为在未来的楼梯中，我们可以使用 n block 堆叠在一起，就像我们有 9 block 砖一样。

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

只是当你只有n block 时，你需要减去无效的情况。

我希望这对您有所帮助——祝您好运!