Python 程式：計算 n 位階梯數的數量

假設我們有一個數字 n，我們需要找到 n 位階梯數的數量。眾所周知，當所有相鄰數字的絕對差為 1 時，該數字稱為階梯數。所以如果一個數字是 123，則它是階梯數，但 124 不是。如果答案非常大，則返回結果模 10^9 + 7。

因此，如果輸入像 n = 2，則輸出將為 17，因為階梯數為 [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]

為了解決這個問題，我們將遵循以下步驟：

• m := 10^9 + 7
• 如果 n 等於 0，則
  • 返回 0
• 如果 n 等於 1，則
  • 返回 10
• dp := 一個大小為 10 的列表，其值為 1
• 迭代 n - 1 次，執行以下操作：
  • ndp := 一個大小為 10 的列表，其值為 0
  • ndp[0] := dp[1]
  • 對於 i 從 1 到 8，執行以下操作：
    • ndp[i] := dp[i - 1] + dp[i + 1]
  • ndp[9] := dp[8]
  • dp := ndp
• 返回 (dp 中所有數字（從索引 1 到結尾）的總和) 模 m

讓我們看看下面的實現以更好地理解：

示例

線上演示

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      if n == 1:
         return 10
      dp = [1] * 10
      for _ in range(n - 1):
         ndp = [0] * 10
         ndp[0] = dp[1]
         for i in range(1, 9):
            ndp[i] = dp[i - 1] + dp[i + 1]
         ndp[9] = dp[8]
         dp = ndp
      return sum(dp[1:]) % m

ob = Solution()
n = 3
print(ob.solve(n))

輸入

3

輸出

32

Arnab Chakraborty

更新於： 2020-12-02

441 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習