Pythonでn桁のステップ数を数えるプログラムを解説

ステップ数とは何か

ある数値 n が与えられたとき、n桁のステップ数（Stepping Number）の個数を求める問題を考えてみましょう。

ステップ数とは、隣り合うすべての桁同士の絶対差がちょうど1になる数のことです。例えば「123」は隣接する桁が 1→2→3 とすべて1ずつ増えているためステップ数ですが、「124」は 2→4 の差が2になるためステップ数ではありません。

また、答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。

入出力の例

入力が n = 2 の場合、出力は 17 になります。これは、2桁のステップ数が以下の17個存在するためです。

12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10

解決のアプローチ：動的計画法（DP）

この問題は、各桁の末尾の数字ごとにステップ数を管理する動的計画法（DP）を使うことで効率的に解けます。dp[i] は「現在の桁数において、末尾の数字が i であるステップ数の個数」を表します。

アルゴリズムの手順

• m := 10^9 + 7 とする
• n が 0 の場合は 0 を返す
• n が 1 の場合は 10 を返す（0〜9 の一桁の数はすべてステップ数）
• 値 1 で埋めたサイズ 10 のリスト dp を作成する
• n − 1 回、以下を繰り返す
  • 値 0 で埋めたサイズ 10 の新しいリスト ndp を作成する
  • ndp[0] := dp[1]（末尾が 0 になるのは直前が 1 の場合のみ）
  • i が 1 から 8 の範囲で ndp[i] := dp[i−1] + dp[i+1]
  • ndp[9] := dp[8]
  • dp := ndp と更新する
• dp のインデックス 1 以降の合計を m で割った余りを返す（先頭が 0 の数は除外）

それでは、実際の実装を見て理解を深めましょう。

Pythonでの実装例

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

まとめ

n = 3 の場合、3桁のステップ数は 32 個存在します。この手法の計算量は O(n × 10)、つまり桁数に対して線形時間で処理できるため、n が非常に大きい場合でも高速に答えを求められます。DPテーブルを毎回新しく作る代わりに、配列を再利用することでメモリ使用量をさらに削減することも可能です。