初めに言います。これはさっぱり動的計画法がわからない人に贈る、そんな記事です。なので目一杯分かりやすくしたいと思います。
そして今回は、動的計画法の定義を漸化式で書くことができるプログラムと思い切って割り切ります。そしてここで何となく動的計画法を分かっていただけたら、そこからまた違う方の記事などを見て勉強して見るといいかもしれません。（ちなみに集めるDPです）
０次元DP（とても簡単）
問、以下のような10個の正の数字が入力される。最大値を出力せよ。
入力
4 9 2 4 7 8 1 5 6 3
出力
9
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[10];
for (int i = 0; i < 10; i++) {
cin >> a[i];
}
int ma = 0;
for (int i = 0; i < 10; i++) {
ma = max(ma, a[i]);
}
cout << ma << endl;//9
}
std::max_element(a,a+10)などでも出来ます。今回注目すべき点はループの度にmaが更新されている点です。個人的にこれを０次元DP、あるいは最大更新法と呼んでおり、この形を使えるようにした結果、動的計画法が分かるようになりました。
簡単ですが、意外にもDPにおいてとんでもなく重要な部分です。シンプルですがほんの少しでもつかめたでしょうか。
また、最小値でも同じようなことできるので試してみてください。（INF=2000000000を用いる）
１次元DP（その１）
問、ｘ軸上に町がある。１番目の町には２人住んでおり、２番目の町には３人住んでいることが知られている。
３番目以降の町には、一つ前の町の人口と、二つ前の町の人口を足した人数が住んでいることが知られている。
N番目の町の人口を求めなさい。（1<=N<=50,かつNは整数）
入力
N = 15
出力
1597
#include <iostream>
using namespace std;
int a[110];//人数を保管する場所。自分はよくsumdpなどと名付ける。
int main() {
int N;
cin >> N;
a[0] = 2;
a[1] = 3;
for (int i = 2; i <= N; i++) {
a[i] = a[i - 1] + a[i - 2];
}
cout << a[N - 1] << endl;
}
初期値 a[0]=2,\ a[1]=3\\
漸化式\ a[i]=a[i-1]+a[i-2]
といった風に考えることができます。そんなに難しく感じた方はいらっしゃらないのではないでしょうか。図で矢印などを書きながらだとより分かりやすいと思います。
これも一つのDPであり、この感触をさらにつかんでいきます。
ここで、この問題の類題を考えた時、漸化式の a[i - 2] の部分に注目すると、数字の部分はループを飛び越さない限りどこにでも設置することが可能であることに気づきます。
簡単に言い換えると、三つ前の町の人口を足したいならa[i - 3]、九つ前の町の人口を足したいならa[i - 9]なども可能です。あとは初期値の値を少しいじって作れそうです。
初級者の私たちにとってこれは大きな発見なのではないでしょうか。ループの直前までのテーブルの値が全て埋まっていれば、a[ i ]=a[i - b]+a[i - c]みたいな式が作れてしまうということです。
これがDPの姿の一つの本質です。
そしてこれにより解決が難しかった問題への扉が開かれます。
一次元DP（その２）
問、五つの数1,6,10,50,234が与えられる。整数Nからこれらの数で引き算を繰り返して、Nを0にしたい。また、五つの数字は何度でも用いて良い。
最小の回数を出力せよ。(1<=N<=100000)
入力
N=19
出力
4
今回は解説から。考えを追いながら説明していきます。
～頭の中～
まず、試しに回数を色々調べてみる。その結果、Nを数の大きい方から引いていく貪欲法は成り立たたないことが分かった。
（例：12は2回で求まる、19は4回で求まるなど)
そして、19という数字を作るための最小回数は、19を18+1と考えると、18を0にする時の最小回数に1回を足したもの、であると考えることができる。
ここでcoudp[19]=coudp[18]+1となりそうだと気づく。(coudpは最小回数を保存している。この+1はcoudp[18]に比べてcoudp[19]は19から1を引く動作の一回分操作が増えるということである。)
さらに、19を0にするための最小回数は、19から1引いた時のcoudp[18]+1、19から6引いた時のcoudp[13]+1、19から10引いた時のcoudp[9]+1があれば19の時の最小回数は分かるのではないだろうかと考える。
すなわちcoudp[19-a[j]]となるのではないだろうか。jはループで回してあげればよい。(a[5]={1,6,10,50,234}の10まで回す)
coudp[18],coudp[17],coudp[16]...coudp[1]。どれもそれ以下の最小回数の値から回数を+1してあげれば求められそうだ。部分的な問題の連続性を確認。
初期値はcoudp[0]=0。これを先ほどのようにcoudp[6]でやってみる。
考えられるのはcoudp[5]+1とcoudp[0]+1。1を使ったときは6回。6を使ったときは1回。
問題なさそうだ。実装に入ろう。
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 2000000000
int coudp[100001];//1～100000におけるの最小回数の記録
//自分はよくcoudpと名付けている。慣れたらdpで問題ない。(countの略)
int main() {
int N;
cin >> N;
int a[5] = { 1,6,10,50,234 };
fill(coudp, coudp + 100000, INF);//minの比較をするためINFで埋める
coudp[0] = 0;
for (int i = 1; i <= N; i++) {//1～Nの時の最小回数をあらかじめ求めるループ
for (int j = 0; j < 5; j++) {
if (i < a[j])break;
coudp[i] = min(coudp[i - a[j]] + 1, coudp[i]);
}
}
cout << coudp[N] << endl;//N=19とすると4が出力される。
}
といった感じです。何となくつかめたでしょうか。ループにより１番目を確定、２番目を確定、３番目を確定・・・それをN番目まで。
あとは聞かれた番号を答えてあげればよいといった感じです。
分からなかった人への補足：18は12+6で求めることが出来ますが、12という数字はDPテーブルに置いて2という数字を持っているだけです。
よって、18はただの2と(a[j]=6を足す1回)で表され、coudp[18]=min(coudp[18-a[j]]+1,coudp[18])=3となるわけです。12は2という数字しか持っていないので過程は分かりません。しかしそれでも答えが求まるこのことを、それまでの経路によらないとよくいいます。
それでもわからなかった人への補足：
上のcoudp[18]=min(coudp[18-a[j]]+1,coudp[18])=3を求める方法ですが、jのループが回っていること確認します。
最初のj=0の時、coudp[18]=min(coudp[18-a[0]]+1,INF)=4(17の時の最小回数+1)
次のj=1の時coudp[18]=min(coudp[18-a[1]]+1, 4 )=3(12の時の最小回数+1)
次のj=2の時coudp[18]=min(coudp[18-a[2]]+1, 3 )=3(8の時の最小回数+1よりも今までのjループの中で計算で行ったものの方が小さいので更新されない)
j=3のときbreakされcoudp[19]へ行く。coudp[19]でもまた同じことを繰り返す。18以下の値の最小回数は全て求めてあるので求まる。
二次元DPやそれ以上の次元のDP
先ほどの一次元がわかると一気に進みます。要はそれ以前の値を用いてdp[i][j]を求めればいいのです。
二次元の場合だとテーブルが平面化し、dp[i][j]=dp[i-a][j-b[k]]+1やdp[i][j]=dp[i-a][j]+dp[i][j-b]などいろいろな書き方があります。
iやjの要素の決定などは練習する必要がありますが、典型的な問題を探して解いていくことがベストだと思います。ここからは自分より実力がある方にお任せします。
おわりに
ここまでくればナップサックDPに手がかかるぐらいまでは来ているはずです。個人的に、一見貪欲法を考えてしまうけど上手くいかない例はDPの物が多いような気がします。
ループで出してある前の値を用いるだけで、今いる位置の値を確定させることができる。そんな感じで気づくとより速いかもしれません。あとは演習を積めば何とかなるはずです。
記事の方はいかがだったでしょうか。長くなりましたが、それなりにしっかり書いたつもりです。ツイッターの方でも競プロで楽しく一喜一憂している自分ですが、皆さんの力になれたら幸いです。