Pythonでn桁のステップ数をカウントするプログラム

数nがあるとすると、n桁のステッピング数を見つける必要があります。隣接するすべての桁の絶対差が1の場合、数値はステッピング番号と呼ばれます。したがって、数値が123の場合、これはステッピング番号ですが、124はそうではありません。答えが非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がn =2の場合、ステップ数は[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：=値1で満たされたサイズ10のリスト
• n-1回繰り返し、実行
  • ndp：=値0で満たされたサイズ10のリスト
  • ndp [0]：=dp [1]
  • 1〜8の範囲のiの場合は、
    • ndp [i]：=dp [i-1] + dp [i + 1]
  • ndp [9]：=dp [8]
  • dp：=ndp
• return（dpのすべての数の合計[インデックス1から終了まで]）mod 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