2025.10.10

記事内に商品プロモーションを含む場合があります

Pythonで学ぶ桁DP（Digit DP）｜桁DPの考え方と実装パターン

Aru

桁DPは、動的計画法（DP）の一種で、数値の桁ごとに状態を分けて管理・遷移していく手法です。特に「数値に関する制約を満たす数の個数を数える」問題でよく登場します。本記事では、桁DPの基本的な考え方から実装方法までを、AtCoderの問題（ABC154 E問題）を題材に具体的に解説します。Pythonを使ったコード例も紹介しながら、桁DPをテンプレート化することで再利用しやすい形にまとめていきます。

Contents

桁DPの基本的な考え方
桁DPの例
- N以下の整数で0でない数字がちょうどK個あるものの個数（ABC154E）
テンプレ化
まとめ

桁DPの基本的な考え方

桁DPとは？

桁DPとは、数値の各桁に注目しながら、状態を遷移させて条件を満たす数を数えるような問題に使われる、動的計画法（DP）の一種です。
特に、「ある上限以下の数のうち、特定の条件を満たす数は何個か？」といった数え上げ問題で威力を発揮します。

たとえば、以下のような問題です：

N以下の数で、0でない数字がちょうどK個ある数はいくつ？
N以下の回文数は何個ある？
各桁の和が特定の値である数は何個？

このような問題では、桁ごとに制約が異なるため、通常のDPでは表現しづらいですが、桁DPは数の桁構造をそのまま活かして処理します。

桁DPの状態に含まれる典型的な要素

桁DPの実装では、状態を表すために複数のパラメータを使います。典型的には以下のような要素が含まれます：

状態変数名	意味
`pos`	現在処理している桁の位置（左から何桁目か）
`tight`	これまでの桁がNと一致しているか（制約フラグ） 1なら上限Nに縛られる、0なら自由
`count`	これまでに条件を満たした回数（例：非ゼロの桁の数）
`leading_zero`（省略可）	先頭が0の状態か（数として未確定な部分）

※問題によって他の変数が追加されることもあります（前の桁の値、桁和、直前の数など）。

なぜ1桁ずつ処理するのか？

人間が数値を左から読んで意味を理解するように、コンピュータも1桁ずつ処理していくことで、「途中までNと一致しているが、次で小さくなるかも」という逐次的な判断が可能になります。

例：N = 6521 のとき、1桁目「6」はNと一致している必要があるが、2桁目「5」は「0〜5」までならOK。ただし「5」以下ならtight状態が続き、「4」以下になったらtightを外して自由にできる、という制御を行います。

この「tight（制約）状態」を使いこなすのが桁DPのキモです。

桁DPの適用パターン

桁DPは、以下のような問題で特によく使われます：

上限がある数（N以下、L〜Rの範囲など）
各桁に制約がある（非ゼロの桁数、偶数だけ、奇数のみなど）
条件を満たす数の「個数」を求める（最適解ではない）

桁DPを使うことで、探索空間が10の桁数乗に収まるため、たとえば20桁程度でも現実的に全探索が可能になります（10⁶～10⁷通り程度）

小まとめ

桁DPは、単にDPの応用ではなく、桁という情報構造を使った問題解決手法です。状態の設計や制約フラグ（tight）を適切に管理できれば、さまざまな「数の性質を満たす個数」の問題を高速に解けるようになります。

次の章では、桁DPをどのような問題に適用すべきか、どんな特徴を持つのかを具体例とともに見ていきます。

桁DPの例

N以下の整数で0でない数字がちょうどK個あるものの個数（ABC154E）

AtCoderのABC154のE問題を例に桁DPの書き方を解説します。

問題の概要

この問題をまとめると以下のようになります。

整数 N（ただし最大100桁）と、整数 K (1 ≦ K ≦ 3) が与えられる
条件
「0でない数字がちょうどK個」の整数で、1 以上 N 以下のものの個数を求める

桁DPのための配列の構造

ここでは以下のような配列を確保しています。

dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(101)]

このdp[i][smaller][j]は以下を意味します

状態パラメータ	意味
`i`	今、何桁目までを見ているか（1-based）
`smaller`	上位の桁で既にNより小さい値を選んでいるか（0: 同じ、1: 小さい）
`j`	これまでに使った0でない数字の個数（最大3）

初期状態はdp[0][0][0]=1です。これは「0桁目まで」「Nと完全に一致」「非ゼロ桁は0個」な状態が1通りという意味になります。

まだ１桁もみていない場合は、0でない数字を１つも使ってないし、Nと完全に一致している（空なので）な状態です。ここに1通りを代入しておくのがポイントです。

メインループ

メインループでは、iを1からNまで、jを0~4までループさせています。jが4までなのはK<=3なのでそれを超えた場合を一応確保するためです。

桁DPの遷移のパターン

パターン①：smaller=1の場合

smaller=1の場合は、既に小さい数字を使っているときは自由に選ぶことが可能です

既にNより小さい数になっているので、どの数字でも選べる
0なら非ゼロ数 j に影響を与えないのでi-1の値をコピー
非ゼロなら j-1 から j に遷移（非ゼロを1つ増やす）

for k in range(10):  # 0〜9を自由に使える
    if k == 0:
        dp[i][1][j] += dp[i-1][1][j]
    else:
        if j != 0:
            dp[i][1][j] += dp[i-1][1][j-1]

パターン②：smaller=0の場合で小さい数字を選ぶ場合

x = int(s[i-1])  # i桁目のNの数字
for k in range(x):
    if k == 0:
        dp[i][1][j] += dp[i-1][0][j]
    else:
        if j != 0:
            dp[i][1][j] += dp[i-1][0][j-1]

s[i-1] より小さい数字を選ぶと smaller=1 にするので、その部分をx-1までループして処理
非ゼロ桁の扱いに応じて j を操作（ここは、smaller=1に近い処理）

パターン③：smaller=0の場合でNと同じ（s[i]）を選ぶ場合

if x == 0:
    dp[i][0][j] = dp[i-1][0][j]
else:
    if j > 0:
        dp[i][0][j] = dp[i-1][0][j-1]

Nと完全に一致する場合の処理
非ゼロであれば j を1増やす

上記の３つを処理することで桁DPの遷移を書くことができます。

smallerもループで処理させることができますが、慣れないうちは３つの状態を個別に書く方が楽です。

プログラム全体

以下、プログラム全体です。最終結果はdp[N][0][K] + dp[N][1][K]となります。

s = input()
K = int(input())


N = len(s)


# dp[n][smaller][num of k]
dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(1, N+1) :
    for j in range(5) :
        # 上位の桁ですでに小さい場合の処理
        for k in range(10) :
            if k == 0 :
                dp[i][1][j] += dp[i-1][1][j]
            else :
                if j != 0 :
                    dp[i][1][j] += dp[i-1][1][j-1]
        
        # s[:i]が同じである場合の処理
        x = ord(s[i-1]) - ord('0')
        for k in range(x) :
            if k == 0 :
                dp[i][1][j] += dp[i-1][0][j]
            else:
                if j != 0 :
                    dp[i][1][j] += dp[i-1][0][j-1]
            
        # この桁もs[i]と同じ場合の処理
        if x == 0:
            dp[i][0][j] = dp[i-1][0][j]
        else :
            if j > 0 :
                dp[i][0][j] = dp[i-1][0][j-1]
        

print(dp[N][0][K] + dp[N][1][K])

テンプレ化

上記のように桁DPは基本３つのパターンを処理することになります。これをテンプレ的に書くと以下のようになります。テンプレではsmallerをループにしています。

def digit_dp(s: str, func, max_k: int):
    """
    桁DPの汎用テンプレート

    Parameters:
    - s: 上限数Nを文字列として与える（例: "6521"）
    - func: 状態遷移のロジックを記述する関数
    - max_k: 状態に含める制約パラメータの最大値（例: 非ゼロ桁数の上限）

    Returns:
    - dp[N][0..1][0..max_k] の配列
    """

    N = len(s)
    dp = [[[0 for _ in range(max_k+2)] for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(1, N+1):
        digit = int(s[i-1])
        for k in range(2):  # smaller: 0(一致中), 1(小さいことが確定)
            for j in range(max_k+1):
                cnt = dp[i-1][k][j]
                if cnt == 0:
                    continue

                # 使える数字の上限（tight制御）
                max_digit = 9 if k == 1 else digit
                for d in range(0, max_digit+1):
                    next_k = 1 if k == 1 or d < digit else 0
                    next_j = func(j, d)
                    if 0 <= next_j <= max_k:
                        dp[i][next_k][next_j] += cnt

    return dp

これを使ってABC154Eのプログラムを記述すると以下になります。

def count_nonzero_digits(prev_count, d):
    if d == 0:
        return prev_count
    else:
        return prev_count + 1

s = input().strip()
K = int(input())

dp = digit_dp(s, count_nonzero_digits, K)

# N桁使って、0（Nと一致）、1（Nより小さい）で非ゼロ桁がK個
print(dp[len(s)][0][K] + dp[len(s)][1][K])

ある程度の桁DPまではこのテンプレで対応できると思いますが、複雑なものを考える場合は、３つのパターンを考えながらABC154Eの例を書き直した方がよいと思います。