Python程序：计算球体避开黑名单台阶到达最低层的路径数量

假设我们有一个值h和一个称为blacklist的数字列表。我们目前位于高度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不在blacklist中，则
        • 如果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))

输入

5, [2, 1]

输出

2

更新于: 2021年10月18日

178 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告