python - 为什么这段 Python 代码在存储缓存索引的总和时会显示 TypeError？

Question

我想探索其他问题来练习 DP(动态编程)。我发现这个是针对楼梯问题的，它类似于 Fib 序列。但是，我所遵循的代码似乎与预计算缓存的总和不符。

据我所知，这是来自 Daily Programming Challenges blogs谈论它是如何工作的。他们使用的代码片段是使用列表推导式的 Pythonic 方式。我已经完成了自己的部分，但我想通过使用 sum 函数并在函数参数中使用一个额外的变量来比较他们的解决方案如何比我的更好。

总结如下:每个条目缓存 [i] 将包含我们可以使用集合 X 到达步骤 i 的方法数。然后，我们将使用与之前相同的循环从零开始构建数组:

这是他们的代码示例

def staircase(n, X):
    cache = [0 for _ in range(n + 1)]
    cache[0] = 1
    for i in range(n + 1):
        cache[i] += sum(cache[i - x] for x in X if i - x > 0)
        cache[i] += 1 if i in X else 0
    return cache[-1]

这是我的代码示例:

def staircase_dp(n):

    dp = [0 for i in range(n + 1)]

    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        val = dp[i - 1] + dp[i - 2]
        dp.insert(i, val)
    return dp[n]

这是我的主要内容:

if __name__ == '__main__':
    steps = 6
    n = 2

    print("Number of ways to use the stairs = {0}".format(staircase(steps, n))) #This will use the example from Daily Programming Challenge and gives TypeError message.
    print("Number of ways to use the stairs = {0}".format(staircase_dp(steps))) #Mine which outputs 13

以他们的例子为例，当我尝试打印出来时，它给了我一条 TypeError 消息:

`Traceback (most recent call last):
  File "staircase.py", line 44, in <module>
    print("Number of ways to use the stairs = {0}".format(staircase_dp(steps, n)))
  File "staircase.py", line 21, in staircase_dp
    cache[i] = sum(cache[i - x] for x in X if i - x > 0)
TypeError: 'int' object is not iterable`

但是，对于我的解决方案，我只是创建一个从 0 到 n 的动态数组。正如我们所知，dp[0] 和 d[1] 将始终给出 1 的值。在第二次迭代之后，我们将开始计算更大的数字并将它们添加到另一个保存 dp[i - 1] + dp[i - 2]。然后将值插入到dp的栈中，之后返回。

我不太明白，因为我只是想在缓存中添加已完成的计算步骤数，然后返回缓存值。这是正确的想法吗？

Answer 1

作为第二个参数传递给函数 staircase 的 X 是 int (2) .

这个:

steps = 6
n = 2
...
staircase(steps, n)

表示 staircase 函数 X 内是 2。这反过来意味着你的回溯中提到的行上的生成器 (cache[i] += sum(cache[i - x] for x in X if i - x > 0)) 会尝试从(迭代)X 获取 x 的值。为了只关注这个问题，我们可以将行简化为(这是从上面的示例中提取的，只是删除与当前问题无关的句法绒毛):

(x for x in 2)

这将引发相同的异常，因为我们无法迭代 oven an int。您不能为 2 中的每个 x(一个 int)做一些事情，因为它没有迭代器(而且实际上没有有意义的项目可以迭代)，因此出现 TypeError 异常。

换句话说:您可能想要迭代该生成器中的其他内容。或者将其他东西(可迭代的)作为第二个参数传递给 staircase。