競技プログラミングを始めてばかりで、世間で呼ばれる「蟻本」を参考にして勉強しているところ、2-3章の動的計画法にぶつかりました。
最初に動的計画法について読んだときは、DPのコードを書けるかどうかどころか概念自体が上手く飲み込めない状態でしたが、インターネット上であちこちのサイトを参考にして理解しようとしたところ、やっと自分なりのDPの問題の解き方の「コツ」を見つけました！ここで、このコツについて少し書き記して、もしできたら他のDPを勉強していて僕のように良く分からない方に役に立ったり、将来の自分宛へのメモになれたらなぁ、と思っています。
では、早速見ていきましょう！
インターネット上でDPに関連し参考になった投稿のリンクを載せました：
- 動的計画法（ナップザック問題）
- じじいのプログラミング
※注意:ここにあるコツというのは典型的な「ナップザック問題」や「コイン問題」などにしか通用しません。複雑なDP問題にまだ手を出せていませんので…
プログラムを組むときの考え方としては、こんな感じです：
1. 再帰を導入した全捜索のプログラムを考える
2. 捜索がかぶりそうな値にdpのリストを導入する
3. （できたら）漸化式を元にプログラムを組む
という感じです。
では、例を見ていきましょう。
*問題：宝物がたくさん収蔵されている博物館に、泥棒が大きな風呂敷を一つだけ持って忍び込みました。盗み出したいものはたくさんありますが、風呂敷が耐えられる重さが限られており、これを超えると風呂敷が破れてしまいます。そこで泥棒は、用意した風呂敷を破らず且つ最も価値が高くなるようなお宝の組み合わせを考えなくてはなりません。
風呂敷が耐えられる重さ W、および博物館にある個々のお宝の価値と重さを読み込んで、重さの総和が W を超えない範囲で価値の総和が最大になるときの、お宝の価値総和を出力するプログラムを作成してください。ただし、価値の総和が最大になる組み合わせが複数あるときは、重さの総和が小さいものを出力することとします。
(W ≤ 1,000, 1 ≤ N ≤ 1,000)
(PCK2004年予選問題の改造)
この問題を全捜索で組みますと、
#include <bits/stdc++.h>
using namespace std;
int n, w;
pair<int, int> takara[1050];
int solve(int w, int p){
int res;
if(p == n)res = 0;
else if(w < takara[p].second)res = solve(w, p+1);
else if(w >= takara[p].second)res = max(solve(w, p+1), solve(w-takara[p].second, p+1) + takara[p].first);
return res;
}
int main(){
scanf("%d", &w);
scanf("%d", &n);
for(int i = 0; i < n; i++)cin >> takara[i].first >> takara[i].second;
cout << solve(w, 0) << endl;
}
となります。
これに動的計画法をいれると、
#include <bits/stdc++.h>
using namespace std;
int n, w;
int dp[1050][1050];
pair<int, int> takara[1050];
int solve(int w, int p){
int res;
if(dp[w][p] != -1)return dp[w][p];
if(p == n)res = 0;
else if(w < takara[p].second)res = solve(w, p+1);
else if(w >= takara[p].second)res = max(solve(w, p+1), solve(w-takara[p].second, p+1) + takara[p].first);
return dp[w][p] = res;
}
int main(){
scanf("%d", &w);
scanf("%d", &n);
for(int i = 0; i < n; i++)cin >> takara[i].first >> takara[i].second;
memset(dp, -1, sizeof(dp));
cout << solve(w, 0) << endl << ;
}
となります。
zensousaku.cppとdp.cppを比べればわかりますが、違いはdpのリストを使っているかどうか、あとはもし既に計算済みの値を関数で要求されると計算済みの値を返すif(dp[w][p] != -1)return dp[w][p];しかありません。
このように、全捜索から簡単にDPにコードを変えることができます。
ご参考になりましたでしょうか。何か投稿の問題点やミスなどを見つけましたら、気軽にコメントを残してください！