農工大アドカレ16日目です！
アドベントカレンダーのページはこちら
Qiitaで記事を書くのも初めてなので、多めに見てもらえると助かります
この記事のターゲット
- 競プロ初心者～中級者 (algorithm rate: 0~900 くらい)
- メモ化再帰・動的計画法のどちらかを学びたての人
動的計画法(DP)とは
動的計画法 (DP: Douteki Plan Dynamic Programming) は、ある大きな問題を小さな問題の集合に分け、その答えを再利用しつつ元の問題を解く、といったアルゴリズム設計方法です。競技プログラミングでは頻繁に出題されており、かなり最初の方に覚え、幅広く使えるテクニックとなっています。
DPを習得するにはこちらのコンテストが便利です $\rightarrow$ Educational DP Contest
さらに詳しいことは他の方がたくさん書いてくれています $\rightarrow$ 動的計画法超入門 - drken様 等
DPを行う場合は事前に $dp[i][j]$ のような多次元配列を用意しておき、漸化式の要領で遷移させて配列を埋めていく方法が一般的です。
DPとメモ化再帰
メモ化再帰はDPの一種で、再帰関数の引数と返り値の対応をメモしておくことで呼び出し回数を大幅に削減する手法です。配列を用いたDPがボトムアップであるのに対し、こちらはトップダウンです。
メモ化再帰を使い始めるきっかけ
ここで、メモ化再帰を使うことになったきっかけについて書いていきます。
競プロを始めたばかりの頃に解いたABC340-C問題 にて、メモ化再帰による解法を学習しました。メモ化再帰を調べるうえでDPの考え方にも触れ、ABC344-D問題 にて同様の方法でACを取ったことで習得しました。
そこから1年以上、すべてのDP問題に対しメモ化再帰を使って解くようになりました。便利なんですよこれが。ちゃんと再帰が追えていればコードの記述量も圧倒的に少なく済みますし、std::mapを使うことで答えの登録も呼び出しも簡単にできるし、遷移の必要があるかを考えなくて済むから当時初心者の僕にとってはこれ以上ない記法だったんです。
おまけに、自分でテンプレートまで作る始末です $\downarrow$
using ll = long long;
using pl = pair<ll, ll>;
map <pl, ll> dp;
vl a;
ll cul_rec(ll x, ll y){
pl tp = {x, y};
if(dp.count(tp)) return dp[tp];//すでに答えが求まっている
ll rt = 0;
/* code */
dp[tp] = rt;//答えをmapに登録
return rt;
}
こちらは2次元の場合のDPに使っていたものですが、必要に応じて引数の数を調節して使用します。1年以上、これでほぼ不自由なくあらゆる問題を解くことができました。
メモ化再帰の限界
ところが先日、ついにメモ化再帰の限界を知ることに。それが ABC431-D問題。重さの制約のもとで価値を最大化させる典型的なナップサック問題で、この問題でDPを使用すると計算量が$O(N^2W) \approx 1.25 × 10^8$ と、かなりギリギリの制約になっていました。
さて、メモ化再帰は再帰のオーバーヘッドが存在するほか、std::mapを使用する関係上毎回の呼び出しごとに$O(log(N^2W))$ で検索が発生します。
つまり全体の計算量は$O(N^2Wlog(N^2W)) \approx 3.36 × 10^9$ に大きめの定数倍がついたものになります。この問題で使ったら間に合わないことは火を見るよりも明らかです。
DP習得まで
前章の日を境に、素直に配列を使ったDPを習得しました。ICPC2025まで時間が無いので、本当に急ピッチでした。
前述したDPコンテストも活用し、配列を作って回す工程にも慣れてきました。
習得したことによって、様々な問題でその恩恵が感じられるようになりました。そのうちの一部を紹介します。
| 提出 | 結果(AC/TLE) | 実行時間 | メモリ使用量 | |
|---|---|---|---|---|
| メモ化再帰解法 | 2025/11 | 15/39 | >2000ms | 238304 KiB |
| DP解法 | 2025/11 | 54/0 | 153ms | 274764 KiB |
※恐らくですが2200ms時点で実行を止めているため、メモリサイズが膨張せずDPよりもメモリ使用量が少なくなっています。基本的にはDPの方がメモリサイズが小さく済みます。
| 提出 | 結果(AC/TLE) | 実行時間 | メモリ使用量 | |
|---|---|---|---|---|
| メモ化再帰解法 | 2024/12 | 15/0 | 355ms | 7448 KiB |
| DP解法 | 2025/11 | 15/0 | 19ms | 4180 KiB |
やはり王道が一番ですね(今更)
ただ、慣れない記法だったので多少の苦労はありました。やはりスポーツと同じで、早いうちについてしまったクセを直すのは難しいんです。皆さんはちゃんと王道に沿いましょうね。
DP vs メモ化再帰
ここまで長々と僕の経験について書いてきましたが、改めてDPとメモ化再帰の比較をしたいと思います。あくまで僕の主観ですが、だいたい合っていると思います。
まず実装上の比較です。
| DP | メモ化再帰 | |
|---|---|---|
| 実装方法 | forループ | 再帰関数 |
| 実装難易度 | 少し複雑 | やや複雑 |
| 可読性 | 高 | 低 |
| 記述量 | 多め | 超少ない |
| 実行時間 | 超短い | 長い |
続いて、データ構造の比較です。
| DP | メモ化再帰 | |
|---|---|---|
| データ構造 | 多次元配列 | std::map |
| out of range | 発生しやすい | 発生しない |
| 枝刈り | 不可 | 可能 |
| 使用メモリ | 小さい | 大きい |
特に競プロをやっていれば、それぞれの表の最後の行は非常に重要です。一方で $10^6$ 程度の計算量で解ける問題なら、実装の速さ重視でメモ化再帰の方が優れているのかな～と思います。再帰関数がスラスラ書けるならね！
まとめ
結論から言うと、素直に配列でDPを実装した方がいいと思います。初心者にとってこれ以上ない記法とは書きましたが、早いうちから変なクセがつく原因となってしまうためあまりオススメしないというのが今のスタンスです。
ただ、当然メモ化再帰にも記述量や枝刈りなどのメリットはありますし、使い分ければもっと上を目指せるのかなって思います。それに、DPでは無理な問題もあります。まさにABC340-C問題もそのひとつでしょう。
この記事を頭の片隅にでも入れてくれればうれしいです。よきDPライフを！