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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告