【AtCoder】辞書型DPのすすめ ― defaultdictで書く動的計画法

1. はじめに

Rin_statisticsです。
最近、競プロ熱が戻ってきたので、以前の記事では触れていなかった「辞書（dict）を使った動的計画法」についてまとめてみます。
今回はPythonを対象とした、辞書型（defaultdict）を用いた動的計画法の解法を紹介します。

↓以前書いた記事
【AtCoder】非ITエンジニアですが入緑しました

2. 辞書型DPとは

私が動的計画法を学び始めたとき、配列を使った一般的な解説がなかなかしっくり来ませんでした。
そこで試行錯誤するうちに、辞書型（dict型）をDPテーブルとして使う方法にたどり着きました。

配列を用いた解法とアルゴリズムの本質は同じですが、以下のような利点があります。

• サイズ管理が不要: dp = [0] * (W+1) のように事前にサイズを決める必要がなく、巨大な座標や疎な状態も扱いやすい。
• キーの柔軟性: 整数だけでなく、文字列やタプルなどをそのまま状態（キー）として扱えるため、直感的に実装できる。
• メモリ効率: 実際に到達する状態のみを保持するため、状態空間が広いが到達できる場所が少ない場合に有利。

一方で、以下のデメリットもあります。

• 実行速度: ハッシュのオーバーヘッドがあるため、単純な配列アクセスに比べると定数倍で遅くなる。
• TLEの危険性: 状態数（辞書のキーの数）が爆発的に増える問題では、計算量とメモリの両面で厳しくなることがある。

3. 辞書型DPの解説

辞書型DPでは、テーブルにすべての状態を事前に確保するのではなく、到達した状態だけを辞書に追加していきます。

基本的な実装ステップは以下の4段階です。

1. テーブルの定義 (defaultdictの利用)
2. 初期値の設定
3. 前の状態の引継ぎ (.copy() でスナップショットをとる)
4. 現在のテーブルの値の更新

3.1 ナップサック問題での実装

最も基本的なナップサック問題を例にコードで示します。

EDPC D - Knapsack 1：$N$個の品物（それぞれ重さ$w$、価値$v$）から重さの合計が$W$以下になるように選び、価値の合計を最大化する問題です。

# https://atcoder.jp/contests/dp/tasks/dp_d
# D - Knapsack 1
from collections import defaultdict

N, W = map(int, input().split())

# 1. テーブルの定義（初期値は0）
dp = defaultdict(int)

# 2. 初期値の設定（重さ0のとき価値0）
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())

    # 3. 前の状態の引継ぎ
    prev_dp = dp.copy()

    # 4. 現在のテーブルの値の更新
    for weight, value in prev_dp.items():
        if weight + w <= W:
            dp[weight + w] = max(dp[weight + w], value + v)

# 結果の出力
print(max(dp.values()))

3.2 なぜ .copy() が必要なのか

上のコードで prev_dp = dp.copy() としている部分が気になった方もいるかもしれません。
これは、前の状態を保存せずに現在の状態のまま値を更新すると、同じステップ内で更新された値を再度使用してしまう（１つの品物を複数回選んでしまう） ためです。

具体例で見てみます。
品物が3つ（A: 重さ1, 価値2／B: 重さ2, 価値3／C: 重さ3, 価値10）、$W=10$ のケースです。

品物A、Bまでは処理され、dp = {0:0, 1:2, 2:3, 3:5} になっているとします。
ここで品物C ($w=3, v=10$) を処理します。

コピーなしの場合（誤り）

品物C(w=3, v=10)を処理：
  key=0 → dp[0+3] = max(dp[3], dp[0]+10) = 10
          (ここで dp[3] が 5 から 10 に上書きされる！)

  key=1 → dp[1+3] = max(dp[4], dp[1]+10) = 12
  key=2 → dp[2+3] = max(dp[5], dp[2]+10) = 13

  key=3 → dp[3+3] = max(dp[6], dp[3]+10)
                              ^^^^^
                              ここで参照するのは本来「品物A+Bの価値(5)」であるべきですが、
                              さっき更新した「品物Cのみの価値(10)」を参照してしまいます。
          = max(0, 10 + 10) = 20

結果、dp[6] = 20 となり、品物Cを2回（重さ3+3）使った不正な値になってしまいます。

コピーなしの場合（正しい）

品物C(w=3, v=10)を処理：
  prev_dp = {0:0, 1:2, 2:3, 3:5}  ← 更新前の状態を保持

  key=0 → dp[3] = max(dp[3], prev_dp[0]+10) = 10
  ...
  key=3 → dp[6] = max(dp[6], prev_dp[3]+10)
                              ^^^^^^^^^
                              こちらは固定された過去の値(5)を参照します。
          = max(0, 5 + 10) = 15

結果、dp[6] = 15 （品物A+B+C）となり正しく計算できます。

このように、copy() を使うことで遷移元を固定し、誤った結果を防ぐことができます。

4. 他の問題への適用

ナップサック問題と同じ「4ステップ」の流れが、異なるタイプの問題にもそのまま使えることを見ていきます。

4.1 文字列をキーにする例（ABC344 D - String Bags）

ABC344 D - String Bags：$N$個の袋からそれぞれ高々1つの文字列を選んで連結し、目標文字列$T$を作るための最小コストを求める問題です。

文字列を扱うDPですが、ナップサック問題と同じ流れで解けます。
配列DPだと「文字列の何文字目まで一致したか」をインデックスにする必要がありますが、辞書型DPなら文字列そのものをキーにできるため、直感的です。

# https://atcoder.jp/contests/abc344/tasks/abc344_d
# D - String Bags
from collections import defaultdict

T = input()
N = int(input())
Ss = [input().split()[1:] for _ in range(N)]

# 1. テーブル定義（最小化問題なので初期値は無限大などにする）
INF = 10**18
dp = defaultdict(lambda: INF)

# 2. 初期値
dp[""] = 0

for S in Ss:
    # 3. 前の状態の引継ぎ
    prev_dp = dp.copy()

    # 4. 更新
    for current_str, cost in prev_dp.items():
        # 袋の中の各文字列 s について試す
        for s in S:
            next_str = current_str + s
            # 目標文字列 T の接頭辞になっている場合のみ遷移させる（枝刈り）
            if len(next_str) <= len(T) and T.startswith(next_str):
                dp[next_str] = min(dp[next_str], cost + 1)

ans = dp[T]
print(-1 if ans == INF else ans)

4.2 タプルをキーにする例（ABC362 E - Count Arithmetic Subsequences）

ABC362 E - Count Arithmetic Subsequences：数列から等差数列となる部分列の個数を、長さごとに求める問題です。

この問題は少し難易度が高い（水色相当）ですが、「数列の状態」をタプルにしてキーに持たせることで解決できます。
※ただし、状態数が多くなりがちなので $N$ が小さい（この問題では$N \le 80$）場合にのみ有効なアプローチです。

# https://atcoder.jp/contests/abc362/tasks/abc362_e
# E - Count Arithmetic Subsequences
from collections import defaultdict

MOD = 998244353
N = int(input())
A = list(map(int, input().split()))

# 1. テーブル定義
# キー：(数列の中身のタプル), 値：その数列ができる通り数
dp = defaultdict(int)

# 2. 初期値（空の数列を1つとみなす、あるいは長さ1から始めるなど実装による）
dp[tuple()] = 1

def is_arithmetic(seq):
    if len(seq) <= 2:
        return True
    diff = seq[1] - seq[0]
    return seq[-1] - seq[-2] == diff

for x in A:
    # 3. 前の状態の引継ぎ
    prev_dp = dp.copy()

    # 4. 更新
    for seq_tuple, count in prev_dp.items():
        # 現在の数列 seq_tuple に x をくっつける
        new_seq = list(seq_tuple)
        new_seq.append(x)

        # 等差数列の条件を満たすなら辞書に追加
        if is_arithmetic(new_seq):
            dp[tuple(new_seq)] = (dp[tuple(new_seq)] + count) % MOD

# 集計
ans = [0] * N
for seq_tuple, count in dp.items():
    length = len(seq_tuple)
    if length >= 1:
        ans[length-1] = (ans[length-1] + count) % MOD

print(*ans)

5. まとめ

辞書型DPで検索してもまとまった記事が少なかったので、今回紹介してみました。

この解法は、DPテーブルのサイズ見積もりが不要で、かつ文字列やタプルなど多様なデータをキーとして扱えるため、「解法を統一的に書ける」 という大きなメリットがあります。

もちろん、実行速度やメモリ制限が厳しい問題では配列DPが必須となることもありますが、もし「DPの実装がどうも苦手だ」「インデックス管理でよくバグる」という方は、この解法で解いてみるのも一つの手だと思います。

以上、ここまでお読みいただきありがとうございました。
誤りや改善点などありましたら、ぜひコメントで教えてください！
（この記事の作成にあたり生成AIをレビューに活用しています）