DP（動的計画法）でコイン問題を解くまでの過程メモ

これは、https://o-treetree.hatenablog.com/entry/DPL1B（明日投稿）の前段階の記事です。動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見ながらとりあえず解けるまでの初心者の思考をメモしたものです。

DPがわからん！

最近暇なので（無職で外出自粛）競技プログラミング AtCoderをやっています。先日AOJにも登録しました。

BFSとかDFSは一応わかったのですが、頻出のDPがわからんので勉強しようと思いました。

↓BFSとかDFSができるようになった記事

o-treetree.hatenablog.com

さて、いろいろ検索しましたが、一番わかりやすかったのはこちら。GoogleBooksで立ち読みできました。（今後見られなくなるかも、知らんけど。買いましょう。）

一応アマゾンのリンクも貼っておきます。アフィ登録してないから僕には一銭も入らんのですけどね。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆,Ozy(協力),秋葉拓哉(協力)
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）

解く問題はAOJのコイン問題です。といっても有名問題なのでいろんなところで（？）見かけます。

上記の本はAOJの開発者が書いてるのでAOJの問題と本の内容がリンクしてます。というわけでコイン問題の直接の解説が書いてあって助かりました。

問題

額面 $ c_1, c_2, \cdots ,c_M $ 円の $ M $ 種類のコインで $ N $ 円を払うとき、最小の枚数は何枚か

制約

$1 ≤ N ≤ 50,000$
$1 ≤ M ≤ 20$
$1 ≤ c_i ≤ 10,000 (1 \le i \le M)$
額面はすべて異なり、必ず1を含む。

入力

N M
c_1 c_2 ... c_M

出力

答えを一行で出力

Ans

DPテーブルの作成

日本円のように $ c = \{1,5,10,50,100,500\} $ のようになっていれば、額面の大きいコインから使えるだけ使っていけば最適解（らしい）ですが、一般にはそういうわけにはいかない（らしい）。

入力例1は $ N=15, M=6, c = \{1,2,7,8,12,50\} $ 。

15 6
1 2 7 8 12 50

額面の大きい方から使おうとすると使うコインは $ \{12, 2, 1\} $ の3枚ですが最適解は $ \{7,8\} $ の2枚です。

DPを使える条件やDPに至る発想については調べている間にちらっと見かけたりしましたがよくわからんので省略。DPでは表を作って、今まで埋めた部分を利用して次々埋めていき求める値を得る。 $$ dp[i][j] := i番目のコイン\dot{ま}\dot{で}使ってj円払うときの最小枚数 $$ として表を作る。

初期値として、コインを使わないで $ j (1 \le j \le N) $ 円払うのは不可能（INF枚必要）だし、0円払うのには0枚でよい。（最小を出すので初期値には適切な無限大をいれておく）

なんとなくわかるところまで記入。

1円払うのは、いくら大きい金額のコインが使えたとしても1円玉1枚が最小。
2円払うのは、1円玉までだったら2枚、2円玉〜までだったら2円玉1枚が最小。
7円払うのは、1円玉までだったら7枚、2円玉までだったら2円x3+1円x1の4枚、7円玉(!?)までだったら1枚が最小。

i↓	j→	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	c_i↓	0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
1	1	0	1	2	3	4	5	6	7
2	2	0	1	1	2	2	3	3	4↓
3	7	0→	1	1	2	2	3	3	1
4	8	0	1	1	2
5	12	0	1	1
6	50	0	1	1

dp[3][7] = 1 というのがどうやって出てきたかというと、2円玉までしか使えなかったら dp[2][7] = 4 を引き継いで4枚必要なのが、7円玉が使えるのでそれ1枚で払える。7円玉1枚で払うというのは、7円玉まで使って0円払う最小枚数 dp[3][0] = 0 から1枚足して7円払えるので dp[3][7] = dp[3][0] + 1 ということである。

7円玉まで使って0円が最適に払えるなら、それに1枚足すことで7円を最適に払える（候補となる）ということ。

実際は上から引き継いだ4と表の左から変化した1との最小値をとって

$$ dp[3][7] = \min (dp[2][7],dp[3][0]+1) = \min (4,1) = 1 $$

まだわかりにくいので表を進める

i↓	j→	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	c_i↓	0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
1	1	0	1	2	3	4	5	6	7	8	9	10	11
2	2	0	1	1	2	2	3	3	4	4	5	5	6
3	7	0	1	1	2	2	3	3	1	2↓	2	3
4	8	0→	1	1	2	2	3	3	1	1	2
5	12	0	1	1
6	50	0	1	1

dp[4][8] = 1 というのは、8円払うのに7円玉までだと dp[3][1] = 1 に7円玉1枚加えて2枚が最小だが、8円玉まで使えれば dp[4][0] = 0 に8円玉1枚加えて1枚が最小。

なんとなくわかってきた気がするので漸化式にする。注意すべきは、表の上から引き継いでくるの（ $ dp[i-1][j] $ ）はいつでもできるが、左にある値を見て求めるの（ $ dp[i][j-c_i]+1 $ ）は $ j < c_i $ の時には不可能ということ。

\begin{align} dp[i][j] = \begin{cases} dp[i-1][j] & (j < c_i) \cr \min (dp[i-1][j], dp[i][j-c_i]+1) & (otherwise) \end{cases} \end{align}

これに従って表を右に、さらに下に埋めていく。

i↓	j→	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	c_i↓	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
1	1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	2	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
3	7	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
4	8	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
5	12	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2
6	50	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2

再掲するが $$ dp[i][j] := i番目のコイン\dot{ま}\dot{で}使ってj円払うときの最小枚数 $$ であった。よって求めたいものは \begin{align} M番目のコインまで使ってN円払うときの最小枚数 &= dp[M][N]\cr &= dp[6][15]\cr &= 2 \end{align} である。実際、15円払うのに最適なのは $ \{7,8\} $ の2枚を出すケースである。（dp[6][15]から逆に辿って支払いの内訳を構成するのは…………できないことはなさそうだが難儀そうだ）

実装

いままで述べたことをコードにする。無限大は、今回 $1 ≤ N ≤ 50,000$ より、50,000より大きければ良い（払う枚数は、1円玉しか持っていないときでも最大50,000枚）。配列のサイズに注意。コインも、何番目が何円かということを配列で管理する（便宜上0番目のコインは0円）。

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define INF 100000 //枚数無限 制約n<=50,000より十分

int main(){
  int N,M;
  cin>>N>>M;
  vi c(M+1, 0); //コインは0番目からM番目まで
  for(int i=1; i<=M; i++){
    cin>>c[i];
  }
  int dp[M+1][N+1]; //i番目までのコインを使ってj円払う最小枚数

  for(int j=1; j<=N; j++){
    //コインを使わないでj円払うのは不可能
    dp[0][j] = INF;
  }
  for(int i=0; i<=M; i++){
    //コインの使い方によらず0円払うのは0枚
    dp[i][0] = 0;
  }

  for(int i=1; i<=M; i++){ //1番目からM番目
    for(int j=1; j<=N; j++){ //1円からN円
      //漸化式の実装
      if(j<c[i]){
        dp[i][j] = dp[i-1][j];
      }else{
        dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]]+1);
      }
    }
  }

  int ans = dp[M][N]; //M番目までのコインを使ってN円払う最小枚数
  cout<<ans<<endl;
}

とりあえずこれでAOJのコイン問題にはACです。（メモリ消費 7200 KB）

DPテーブルを1次元にできる

DPテーブルを埋めていくとき、dp[i][j]が分かってしまえばdp[i-1][j]は用済みだということは漸化式からわかる通りである（実際に手を動かしてみてもわかる）。

ということは、1次元の配列にして、使えるコインの枚数が増えるごとに上書きしてしまえば良い。あらたにDPテーブルを以下のように定める

\begin{align} dp[j] := j円払うときの最小枚数\cr dp[j] = \begin{cases} dp[j] & (j < c_i) \cr \min(dp[j], dp[j-c_i]+1) & (otherwise) \end{cases} \end{align}

これをプログラムにすると次のようになる

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define INF 100000 //枚数無限 制約n<=50,000より十分

int main(){
  int N,M;
  cin>>N>>M;
  vi c(M+1, 0);
  for(int i=1; i<=M; i++)cin>>c[i];

  vi dp(N+1); //j円払う最小枚数
  for(int i=0; i<=N; i++)dp[i] = INF; //初期値無限枚必要
  dp[0] = 0; //0円払うのは0枚

  for(int i=1; i<=M; i++){
    for(int j=1; j<=N; j++){
      //上記の漸化式の otherwise のケースだけ書き換えが発生しうる
      if(j>=c[i])dp[j] = min(dp[j], dp[j-c[i]]+1);
    }
  }
  int ans = dp[N];
  cout<<ans<<endl;
}