Pythonでブラックリストに登録されたステップを回避することにより、ボールが最低レベルに落ちる可能性のある方法の数をカウントするプログラム

値hとブラックリストと呼ばれる数値のリストがあるとします。現在、高さhにあり、小さなボールを高さ0まで移動するゲームをプレイしています。これで、偶数ラウンド（0から開始）で、ボールを1、2、または4段下に移動できます。そして、奇数ラウンドでは、ボールを1、3、または4段下に移動できます。一部のレベルはブラックリストに登録されています。したがって、ボールがそこに到達すると、すぐに死んでしまいます。ボールが高さ0で下に移動できる方法の数を見つける必要があります。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がh =5 blacklist =[2、1]の場合、出力は2になります。これは、ラウンド0で、最初に1ステップ（5から4）移動し、次のラウンドで4から0に移動するためです。別の可能な方法は、ラウンド0で、2つのステップ（5から3）を移動し、次のラウンドで3から0にすることです。

これを解決するには、次の手順に従います-

• ブラックリスト：=ブラックリストの要素からの新しいセット
• 0がブラックリストにあるか、hがブラックリストにある場合、
  • 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
• return 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