1.初めに

・アルゴリズムを学ぶために、競技プログラミングを始めました。
・AOJのコースをやっていくので、その備忘録を残します。

1.1.前提知識

・組み合わせ最適化問題の解法の一つとして「動的計画法(DP)」というものがあります。

1.1.1動的計画法(DP)って何？

ある問題を小さな問題に分けて解いていく手法

・組合せ最適化問題では「DPテーブル」という表の値を埋めていくことで、正解に辿り着けます。

2.コイン問題

2.1問題

額面が$c_1, c_2,..., c_m$　円の　$m$　種類のコインを使って、 $n$ 円を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。

入力

$n$ $m$
$c_1$ $c_2$ $...$ $c_m$

１行目に整数 $n$ と整数 $m$ が１つの空白区切りで１行に与えられます。２行目に各コインの額面が１つの空白区切りで１行に与えられます。

出力

コインの最小枚数を１行に出力してください。

制約

$1 ≤ n ≤ 50,000$
$1 ≤ m ≤ 20$
$1 ≤ 額面 ≤ 10,000$

額面はすべて異なり、必ず1を含む。

2.2.DPテーブルを作る

・入力例1が

15 6
1 2 7 8 12 50

となってるので、これを元にDPテーブルを作っていきます。

i：使えるコインの枚数(枚)
j：支払う金額(円)
として
$$\boldsymbol{dp[i][j]=i番目までのコインを使ってj円支払うとき、使用するコインの枚数の最小値}$$
として表を埋めていきます。

・dp[i][j]の初期値としてinf(無限大)の値を入れておきます。(見にくくなるので最初の行だけ記入してます。)

	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
c1↓	0	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf
1	1
2	2
7	3
8	4
12	5
50	6

・i=1,j=1の時：(1枚目までのコインを使って1円払うとき)
→1枚目までのコインは{1}だけなので、その１のコインを使って1円払う時、使用するコインの枚数の最小値は「1」。

	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
c1↓	0	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf
1	1		1
2	2
7	3
8	4
12	5
50	6

・i=3,j=4の時：(3枚目までのコインを使って4円払うとき)
→3枚目までのコインは{1,2,7}なので、その3のコインを使って4円払う時、2円を2枚使うのが最小の枚数なので、使用するコインの枚数の最小値は「2」。

	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
c1↓	0	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf
1	1		1
2	2
7	3					2
8	4
12	5
50	6

・こんな感じで、ある程度埋めていきます。

	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
ci↓	0	inf	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
7	3	0	1	1	2	2	3	3	1	2
8	4	0	1	1	2	2	3	3	1	1
12	5	0	1	1	2	2	3	3	1	1
50	6	0	1	1	2	2	3	3	1	1

・このように埋めていくと次の①と②の規則性に気がつきます。

①：j(支払う金額)がci(i番目のコイン)よりも大きくなってしまったら(j<ci)

それ以降のコイン($ci$)は使わないので表の上の値($dp[i-1][j]$)をそのまま$dp[i][j]$に入れる。

	i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
ci↓	0	inf	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
7	3	0	1	1	2	2	3	3	1	2
8	4	0	1	1	2	2	3	3	1	1
12	5	0	1	1	2	2	3	3	1	1
50	6	0	1	1	2	2	3	3	1	1

②：それ以外は

「同じ行の左にある値($dp[i][j-ci]$)に1を加えた値($dp[i][j-c]+1$)」又は、「表の上の値($dp[i-1][j]$)」のどちらか小さいほうを$dp[i][j]$に入れる。

・i=3,j=9の時(3枚目までのコインを使って9円払うとき)
→「同じ行の左にある値($dp[3][9-7]=1$)に1を加えた値( $dp[3][9-7]+1=2$ )」又は、「表の上の値($dp[3-1][9]=5$)」のどちらか小さいほうを$dp[3][9]$に入れる。

・①、②を式で表すと

dp[i][j] = \left\{
\begin{array}{ll}
dp[i-1][j] & (j<ci) \\
min(dp[i-1][j], dp[i][j-ci]) & (otherwise)
\end{array}
\right.

となる。

4.実装

#入力値を取得
n,m=map(int,input().split())
c = list(map(int,input().split()))

"""
使えるコインの枚数(m)を行、支払う金額の値(n+1)列として
使用するコインの枚数の最小値(dp[i][j])を要素にもつ行列を作る。
(0円の支払いを加えるため→n+1)
"""
#初期値としてdp表の値は全てinf(無限大)に設定
inf = float("inf")
dp=[[inf for x in range(n+1)] for y in range(m)]

#支払う金額が0の時、使うコインの枚数は0枚
for k in range(m):
  dp[k][0] = 0

#(j<ci)と(それ以外)の場合に分けてdp[i][j]を埋めていく
for i in range(m):
  for j in range(n+1):
    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)
print(dp[m-1][n])

4.1.DP表を一次元にして考える

・1番左上のマスから、右方向に順番に$dp[i][j]$を埋めていくと考えます。
・$d[i][j]$の値を求めるのに必要なのは$dp[i-1]$の行だけであってそれ以前の$dp[i-2]$の行は必要ありません。

・つまり、一行だけを考えて、$dp[i][j]$の値がわかったらその値を上書きして入れてしまえば効率的に表を埋めていくことができます。

・例えば上の表では、3行目の$dp[3][8]$まで更新されています。
　　　　　　　↓

　　　　　　　↓
・次求めたい値(更新する値)が$dp[3][9]$だとします。
　　　　　　　↓
・$dp[3][9]=2$と分かりました。
　　　　　　　↓
・更新！！
　　　　　　　↓

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
3	0	1	1	2	2	3	3	1	2	2	5	5	6	6	7	7

・みたいな感じで埋めていきます。

・つまり、支払う金額がjの時のコインの最小枚数は
$$
dp[j] = min(dp[j], dp[j-ci])
$$
と表すことができます。

4.2.実装(一次元バージョン)

#入力値を取得
n,m=map(int,input().split())
c = list(map(int,input().split()))

#一次元の行列のみで表せる
inf = float("inf")
dp=[inf for x in range(n+1)]

#最初の要素は0円の支払いだから使うコインは0枚
dp[0]=0

#コインの種類の中で回す
for i in c:
  #コインの種類の値から支払う額の+1まで回す(支払う金額0円の時を含めているため)
  for j in range(i,n+1):
    #要素を埋める
    dp[j] = min(dp[j],dp[j-i]+1)
print(dp[n])

参考サイト