用 Python 编写程序，计算球通过避开列入黑名单的步骤落到最低层的方法数

pythonserver side programmingprogramming更新于 2026/1/18 21:00:17

假设我们有一个值 h 和一个名为黑名单的数字列表。我们目前在高度 h，正在玩一个游戏，将一个小球移动到高度 0。现在，在偶数轮(从 0 开始)中，我们可以将球向下移动 1、2 或 4 个台阶。而在奇数轮中，我们可以将球向下移动 1、3 或 4 个台阶。有些层级列入了黑名单。所以如果球到达那里，它会立即死亡。我们必须找到球在高度 0 处向下移动的方式数量。如果答案太大，则对结果取 10^9 + 7 的模。

因此，如果输入为 h = 5 blacklist = [2, 1]，则输出将为 2，因为在第 0 轮，先移动一步(从 5 到 4)，然后在下一轮从 4 到 0。另一种可能的方式可能是在第 0 轮，移动两步(从 5 到 3)，然后在下一轮从 3 到 0。

为了解决这个问题，我们将遵循以下步骤 −

blacklist := 来自 blacklist 元素的新集合
如果 0 在 blacklist 中或 h 在 blacklist 中，则
- 返回 0
dp := 大小为 h 的列表，并且其中包含在每个索引处存储对 [0, 0]
dp[0] := [1, 1]
m := 10^9 + 7
对于范围从 1 到 h 的 i，执行
- 对于 [1, 2, 3, 4] 中的每个 x，执行
  - 如果 i - x >= 0 且 i - x 不在黑名单中，则
    - 如果 x 不等于 3，则
      - dp[i, 0] := dp[i, 0] + dp[i - x, 1]
    - 如果 x 不等于 2，则
      - dp[i, 1] := dp[i, 1] + dp[i - x, 0]
  - dp[i, 0] := dp[i, 0] mod m
  - dp[i, 1] := dp[i, 1] mod m
返回 dp[h, 0]

示例

让我们看看下面的实现以便更好地理解 −

def solve(h, blacklist):
   blacklist = set(blacklist)
   if 0 in blacklist or h in blacklist:
      return 0
   dp = [[0, 0] for i in range(h + 1)]
   dp[0] = [1, 1]
   m = 10 ** 9 + 7
   for i in range(1, h + 1):
      for x in [1, 2, 3, 4]:
         if i - x >= 0 and i - x not in blacklist:
            if x != 3:
               dp[i][0] += dp[i - x][1]
            if x != 2:
               dp[i][1] += dp[i - x][0]
         dp[i][0] %= m
         dp[i][1] %= m
   return dp[h][0]

h = 5
blacklist = [2, 1]
print(solve(h, blacklist))