蟻本2-3は動的計画法（DP, Dynamic Programming）です．難しくなりました．
「再帰関数の処理」が「漸化式」で表せることがポイントです．漸化式の立て方は一つではないので，問題にあわせて計算量が少なくなる漸化式を選択する必要があります．
読めば，漸化式の内容は理解できるのですが，つくるのはなかなか難しいです．
自分が発想できるように，考え方やコードを書籍のものとは変えている部分があります（書籍の考え方も合わせて解説します）．
背景：蟻本をやります - 競プロはじめました
テキスト：
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41oruV+aJIL._SL500_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
【2021.04.21】1周．
01ナップサック問題
【入力】4
2 3
1 2
3 4
2 2
5
【出力】
7
いくつか方法が紹介されています．
ロジックは再帰的な方法で考えるのがわかりやすく，処理は漸化式で行うのがわかりやすそうです．
方法1：再帰＋メモ化
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [[0]*(w+1) for _ in range(n+1)] def rec(i, j): if dp[i][j] > 0: return dp[i][j] if i == n: res = 0 elif j < wl[i]: res = rec(i+1, j) else: res = max(rec(i+1, j), rec(i+1, j-wl[i]) + vl[i]) dp[i][j] = res return res print(rec(0, w))
【ポイント】
再帰の考え方をしっかり理解しておくことが，後の方法を理解するために必要です．
「この問題が再帰で解けるか」という問題は，「帰納的な方法で解けるか」ということに相当します．
そこで，もし$n$番目の品物を除いた問題に対して答えがわかっているとして，その値をもとに品物が$n$個の問題を解く方法を考えます．
選択肢としては，①$n$番目の品物を加えない，②$n$番目の品物を加える，だけです．したがって，①と②のうち大きい方が，品物が$n$個の問題の答えとなります．
ここで，必要な情報は$n$番目の品物の重さを$w[n]$とするとき
- 品物：$n-1$個，重さ$W$以下
- 品物：$n-1$個，重さ$W-w[n]$以下
また，このコードから，
&\mathrm{dp}[i][j]
=\mathrm{rec}(i,j) \\
&=
\begin{cases}
\, 0 & (i=n)\\
\, \mathrm{dp}[i+1][j] & (j < w[i]) \\
\, \max\bigl(\mathrm{dp}[i+1][j], \mathrm{dp}[i+1][j-w[i]] + v[i] \bigr) &(\text{otherwise})
\end{cases}
\end{aligned}
方法2：漸化式①
意図しない参照が起こったときにエラーになるよう，dpの初期化を文字列で行いました．n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [['']*(w+1) for _ in range(n+1)] dp[n] = [0]*(w+1) for i in reversed(range(n)): for j in range(w+1): if j < wl[i]: dp[i][j] = dp[i+1][j] else: dp[i][j] = max(dp[i+1][j], dp[i+1][j-wl[i]] + vl[i]) print(dp[0][w])
【ポイント】
- dp[i][j]=品物($ > i$番目)から重さがj以下となるように選んだときの最大価値
- $0\leq j \leq W$
- 品物の添字は$1\leq i \leq n$である．$n$番目を超える品物はないので$\mathrm{dp}[n][j]=0$（あるいは，こうすれば下の式から$dp[n-1][j]=0$が正しく決まることが確認できる）．
- $0\leq i \leq n-1$に対して
\begin{aligned}となる．これは，$i$については大きな添字を参照し，jについては小さな値を参照する漸化式となっている．
&\mathrm{dp}[i][j] \\&=
\begin{cases}
\, \mathrm{dp}[i+1][j] & (j < w[i]) \\
\, \max\bigl(\mathrm{dp}[i+1][j], \mathrm{dp}[i+1][j-w[i]] + v[i] \bigr) &(\text{otherwise})
\end{cases}
\end{aligned}
このように，iに関するループが逆順になるのは，①この漸化式が最初の再帰関数の処理をもとにつくられており，②再帰関数の処理はiが最も大きいところ（i=n）から小さくなる方へ決まっていくことが背景にある．
一方で，次の「方法3，4」ではiが小さい方から大きい方へ動くループになる．
方法3：漸化式②
漸化式の立て方は，dp[i][j]の定義の仕方で変わってくる．- 品物の添字は$0\leq i \leq n-1$
- dp[i][j]=品物($< i$番目)から重さがj以下となるように選んだときの最大価値
&\mathrm{dp}[i+1][j] \\
&=
\begin{cases}
\, \mathrm{dp}[i][j] & (j < w[i]) \\
\, \max\bigl(\mathrm{dp}[i][j], \mathrm{dp}[i][j-w[i]] + v[i] \bigr) &(\text{otherwise})
\end{cases}
\end{aligned}
※以上の考え方を，再帰関数で考えると，（方法1では$i=0$から考えたのに対し）$i=n$から考えることになる．
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [['']*(w+1) for _ in range(n+1)] dp[0] = [0]*(w+1) for i in range(n): for j in range(w+1): if j < wl[i]: dp[i+1][j] = dp[i][j] else: dp[i+1][j] = max(dp[i][j], dp[i][j-wl[i]] + vl[i]) print(dp[n][w])
さらに，漸化式で，左辺の$\mathrm{dp}[i+1][j]$が参照しているのは，$i$の一つ前のループの$j, j-w[i] (\leq j)$なので，$j$のループを逆向きにして，大きな$j$から値を更新していけば，$i$の添字無しでよいことがわかる．このとき，$i$の添字がないと，if j < wl[i]: の部分はdp[j] = dp[j]と値を変えないため不要になる（ループから除いてよい）．
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [0]*(w+1) for i in range(n): for j in reversed(range(wl[i], w+1)): dp[j] = max(dp[j], dp[j-wl[i]] + vl[i]) print(dp[w])
方法4：状態遷移
漸化式は，dpの更新はどうすればよいか？（左辺のdpはどう表せばよいか？）という考えを表したものだった．今度は，あるdpの値がどのdpに影響するか？（遷移するか？）を考える．つまり，漸化式では左辺が主役だったが，ここでは右辺が主役となる．
$\textcolor{red}{\mathrm{dp}[i][j]}$が影響し得るのは，$\mathrm{dp}[i+1][j]$（品物を入れない場合）と$\mathrm{dp}[i+1][j + w[i]]$（品物を入れる場合）である．これを式で書くと
\mathrm{dp}[i+1][j]
&=\max(\mathrm{dp}[i+1][j], \textcolor{red}{\mathrm{dp}[i][j]}) \\
\mathrm{dp}[i+1][j + w[i]]
&=\max\bigl(\mathrm{dp}[i+1][j + w[i]], \textcolor{red}{\mathrm{dp}[i][j]} + v[i] \bigr) \quad (j + w[i] \leq W)
\end{aligned}
ここで，すでに入っている値より大きな場合に値を更新する処理にしているのは，あらゆる遷移方法のなかで最大値をとりたいからである．
また，左辺より右辺のほうがiの値が小さい．よって，iのループの中にjのループが入っていれば，$\mathrm{dp}[i+1][\cdot]$の値が確定する前に他に参照されることはない．
方法5：ループ変数の変更（01ナップサック問題 - その2）
【コード】n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value jmax = n * max(vl) dp = [['']*(jmax+1) for _ in range(n+1)] dp[0] = [float('inf')]*(jmax+1) dp[0][0] = 0 for i in range(n): for j in range(jmax+1): if j < vl[i]: dp[i+1][j] = dp[i][j] else: dp[i+1][j] = min(dp[i][j], dp[i][j-vl[i]] + wl[i]) print(max([j for j in range(jmax+1) if dp[n][j]<=w]))
【ポイント】
これまでは，「①品物の個数iを0からnまで増やしていきながら，それぞれの個数で重さがj以下の場合の最大価値を求め」，「②個数n，重さW以下のときの価値の最大値を答えとする」としました．この方法では，jのループで変化するのは重さでした．
しかし，重さでループすると計算量が多くなってしまう場合は，後者の方法で価値でループさせる方法が有効になります．
そこで，jのループで価値を変化させることを考えます．考えている問題は「重さをできるだけ小さくしながら，価値を大きくする」と言えるので，「①品物の個数iを0からnまで増やしていきながら，それぞれの個数で価値がj以下（*1）の場合の最小重さを求め」，「②個数n，重さがW以下となるもののうちで，価値の最大値を答えとする」としても良いことがわかります．
漸化式は
- 品物の添字は$0\leq i \leq n-1$
- dp[i][j]=品物($< i$番目)から価値がjとなるように選んだときの最小重さ（解なしの場合は，次ステップ以降に選ばれないように∞とすればよい）
\begin{cases}
\, \mathrm{dp}[0][0]=0\\
\, \mathrm{dp}[0][j]=\infty & (j\neq 0)
\end{cases}
\end{aligned}
&\mathrm{dp}[i+1][j] \\
&=
\begin{cases}
\, \mathrm{dp}[i][j] & (j < v[i]) \\
\, \textcolor{red}{\min}\bigl(\mathrm{dp}[i][j], \mathrm{dp}[i][j-\textcolor{red}{v[i]}] + \textcolor{red}{w[i]} \bigr) &(\text{otherwise})
\end{cases}
\end{aligned}
個数制限なしナップサック問題
【入力】3
3 4
4 5
2 3
7
【出力】
10
【コード】
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [['']*(w+1) for _ in range(n+1)] dp[0] = [0]*(w+1) for i in range(n): for j in range(w+1): if j < wl[i]: dp[i+1][j] = dp[i][j] else: dp[i+1][j] = max(dp[i][j], dp[i+1][j-wl[i]] + vl[i]) print(dp[n][w])
【ポイント】
01ナップサック問題の漸化式②を，個数制限なしの場合に変えていきます．
- 品物の添字は$0\leq i \leq n-1$
- dp[i][j]=品物($< i$番目)から重さがj以下となるように選んだときの最大価値
&\mathrm{dp}[i+1][j] \\
&=\max\Bigl\{\mathrm{dp}[i][j-\textcolor{red}{k}\cdot w[i]] + \textcolor{red}{k}\cdot v[i] \,\Bigl|\,
\substack{j- \textcolor{red}{k}\cdot w[i] \geq 0 \\[0.5ex] \textcolor{red}{k}=0,1,2,...,} \Bigr\}
\end{aligned}
次の変形で，$k$を消去した漸化式が得られます．
&\mathrm{dp}[i+1][j] \\
&=\max\biggl\{ \mathrm{dp}[i][j],
\max\Bigl\{\mathrm{dp}[i][j-k\cdot w[i]] + k\cdot v[i] \,\Bigl|\,
\substack{j- k\cdot w[i] \geq 0 \\[0.5ex] k=\textcolor{red}{1},2,...,} \Bigr\} \biggl\} \\
&=\max\biggl\{ \mathrm{dp}[i][j],
\max\Bigl\{\mathrm{dp}[i][(j-w[i])-k\cdot w[i]] + k\cdot v[i] \,\Bigl|\,
\substack{(j-w[i]) - k\cdot w[i] \geq 0 \\[0.5ex] k=\textcolor{red}{0},1,2,...,} \Bigr\} +v[i] \biggl\} \\
&=\max\Bigl\{\mathrm{dp}[i][j], \mathrm{dp}[i\textcolor{red}{+1}][j-w[i]]+v[i] \Bigr\}
\end{aligned}
01ナップサック問題の場合とは，+1の部分が異なります．01ナップサックの場合は，1個しかない品物を入れれば$i$が増えたのに対し，個数制限がなければ増えないためです．
01ナップサック問題の場合と同じように，再帰的な考え方で「入れる場合と入れない場合の大きい方をとる」と考えれば，この最終的な漸化式が（上の式変形なく）得られるはずです．
次に，01ナップサック問題の場合と同じように，$\mathrm{dp}$の$i$の添字が消せないか考えてみます．漸化式の左辺$\mathrm{dp}[i+1][j]$が参照している添字は，$i$の一つ前のループに関しては$j$，$i$の同じループに関しては$j-w[i] < j$です．したがって，$j$が小さい方からループを回せば（$i+1$の添字に値を更新していけば），$i$の添字は不要です．
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [0]*(w+1) for i in range(n): for j in range(wl[i], w+1): dp[j] = max(dp[j], dp[j-wl[i]] + vl[i]) print(dp[w])
他のテクニックとして，$i$に関する添字を「偶奇の2種類」だけ用意する方法が紹介されています．
つまり，漸化式
&\mathrm{dp}[i+1][j] \\
&=\max\Bigl\{\mathrm{dp}[i][j], \mathrm{dp}[i+1][j-w[i]]+v[i] \Bigr\}
\end{aligned}
偶数・奇数をビットで判定すれば，次のコードが書けます（&1のかわりに%2でも良いです）．
n = int(input()) l = [list(map(int, input().split())) for _ in range(n)] w = int(input()) wl = [l[i][0] for i in range(n)] # weight vl = [l[i][1] for i in range(n)] # value dp = [['']*(w+1) for _ in range(2)] dp[0] = [0]*(w+1) for i in range(n): for j in range(w+1): if j < wl[i]: dp[(i+1)&1][j] = dp[i&1][j] else: dp[(i+1)&1][j] = max(dp[i&1][j], dp[(i+1)&1][j-wl[i]] + vl[i]) print(dp[n&1][w])
共通最長部分列問題
【入力】4
4
abcd
becd
【出力】
3 (bcd)
【コード】
n = int(input()) m = int(input()) s = input() t = input() dp = [[0]*(m+1) for _ in range(n+1)] dp2 = [['']*(m+1) for _ in range(n+1)] # 追加 for i in range(n): for j in range(m): if s[i] == t[j]: dp[i+1][j+1] = dp[i][j] + 1 dp2[i+1][j+1] = dp2[i][j] + s[i] # 追加 else: dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) # 追加 if dp[i][j+1] > dp[i+1][j]: dp2[i+1][j+1] = dp2[i][j+1] else: dp2[i+1][j+1] = dp2[i+1][j] print('{} ({})'.format(dp[n][m], dp2[n][m]))
【ポイント】
漸化式をたてられるかどうかですね．$\mathrm{dp}[0][j]=\mathrm{dp}[i][0]=0$で
&\mathrm{dp}[i+1][j+1] \\
&=
\begin{cases}
\, \mathrm{dp}[i][j] + 1 & (s_{i+1}=t_{i+1}) \\
\, \max\bigl(\mathrm{dp}[i][j+1], \mathrm{dp}[i+1][j] \bigr) & (s_{i+1}\neq t_{i+1})
\end{cases}
\end{aligned}
個数制限付き部分和問題
【入力】3
3 5 8
3 2 2
17
【出力】
Yes ([3, 3, 3, 8])
【コード】
n = int(input()) a = list(map(int, input().split())) m = list(map(int, input().split())) k = int(input()) dp = [-1]*(k+1) dp[0] = 0 ans_list = [[[]]*(k+1) for _ in range(n+1)] # 追加 for i in range(n): for j in range(k+1): if dp[j] >= 0: dp[j] = m[i] ans_list[i+1][j]=ans_list[i][j] # 追加 elif j-a[i] >= 0 and dp[j-a[i]] >= 0: dp[j] = dp[j-a[i]] - 1 ans_list[i+1][j]=ans_list[i+1][j-a[i]] + [a[i]] # 追加 else: dp[j] = -1 if dp[k] >= 0: print('Yes ({})'.format(ans_list[n][k])) else: print('No')
【ポイント】
$\mathrm{dp}$を
- $a_{i}$の添字は$i=0,1,…,n-1$
- $\mathrm{dp}[i][j]=a_{0},a_{1},…,a_{i-1}$までで$j$をつくるときに余る$a_{i-1}$の最大個数（つくれないときは-1とする）．$\mathrm{dp}[0][0]=0$，$\mathrm{dp}[0][j]=-1\,(j\neq 0)$．
$\mathrm{dp}[i+1][j]$に遷移できるのは，$\mathrm{dp}[i][j]$（に対して何もしない場合）と$\mathrm{dp}[i+1][j-a_{i}]$（に対して$a_{i}$を加える場合）です．ただし，遷移できる条件として，遷移前の状態がつくれること（値が-1でない），前の状態が存在すること（配列の添字範囲）が必要です．
以上を考慮すると，漸化式は，
& \mathrm{dp}[i+1][j] \\
&=
\begin{cases}
\, m_{i} & (\mathrm{dp}[i][j] \geq 0) \\
\, \mathrm{dp}[i+1][j-a_{i}] -1
& (j - a_{i}\geq 0 \,\text{and}\, \mathrm{dp}[i+1][j-a_{i}] \geq 0) \\
\, -1 & (\text{otherwise}) \\
\end{cases}
\end{aligned}
また，漸化式で参照しているのは，①ひとつ前の$i$ループの同じ$j$，②同じ$i$ループの$j-a_{i} ( < j )$だから，$j$を小さい方から更新していけば$i$の添字は不要です．
最長増加部分列問題
【入力】5
4 2 3 1 5
【出力】
3 ([2, 3, 5])
方法1：漸化式①
- $\mathrm{dp}[i]=$最後が$a_{i}$である増加部分列の長さの最大値
\mathrm{dp}[\textcolor{red}{i}]
=\max\bigl(1, \max\{ \mathrm{dp}[j]+1\,|\, j < \textcolor{red}{i}, a_{j} < a_{\textcolor{red}{i}} \}\bigr)
\end{aligned}
ただし，$\{ \mathrm{dp}[j]+1 \,|\, j < i \,\text{and}\, a_{j} < a_{i} \}=\emptyset$となる可能性があることに注意が必要です．
n = int(input()) a = list(map(int, input().split())) res = 0 ans_index = 0 # 追加 dp = ['']*n dp[0] = 1 ans_list = [[]]*n # 追加 for i in range(n): dp[i] = 1 ans_list[i] = [a[i]] # 追加 for j in range(i): if a[j] < a[i] and dp[i] < dp[j]+1: dp[i] = dp[j]+1 ans_list[i] = ans_list[j] + [a[i]] # 追加 if res < dp[i]: res = dp[i] ans_index = i # 追加 print('{} ({})'.format(res, ans_list[ans_index]))
方法2：漸化式②
漸化式①の「$a_{i}$」と「部分列の長さ」の役割を逆転させることを考えます．- $\mathrm{dp}[i]=$長さが$i+1$である増加部分列の最終要素の最小値(存在しない場合は∞)
$\mathrm{dp}$を$\infty$で初期化してあるとし，$a_{j}$を$j$の小さい方から順に，$\mathrm{dp}[i]$を$i$の小さい方から順に見ていくことを考えます．$i=0$の場合に，すでに入っている$\mathrm{dp}[0]$の値よりも$a_{j}$のほうが小さければ，$\mathrm{dp}[0]=a_{j}$と更新されます．$i\neq 0$の場合には，もし，$\mathrm{dp}[i-1] < a_{j}$となる$i$があれば，$\mathrm{dp}[i]=\min(\mathrm{dp}[i], a_{j})$と更新されます（$\mathrm{dp}[-1]=-\infty$と考えれば，$i=0$の場合も同じ更新ルールになる）．
最終的な答えは$\max\{i\,|\, \mathrm{dp}[i] < \infty \} + 1$です．
注：この方法で更新されたDPテーブルは，部分列の具体例にはなりません．
さて，$\mathrm{dp}[i]$は$\mathrm{dp}[i-1]$よりも大きな値で更新されるので，$\infty$を除けば単調増加です．さらに，もし$a_{j}$によって$\mathrm{dp}[i]$が更新されるとすると，$a_{j} < \mathrm{dp}[i](\text{更新前}) \leq \mathrm{dp}[i+1]$なので，$ \mathrm{dp}[i+1]$以降の更新は起こりません．つまり，各$a_{j}$に対して更新は1回以下です．
したがって，$\mathrm{dp}[i]$の順序を保ったまま$a_{j}$を挿入できる箇所を$O(n\log n)$で教えてくれる（二分探索）bisectを使えば，ループを使うより高速なコードが書けます（蟻本をPythonで (初級編) - Qiita）．このとき，更新回数$0$回の$a_{j}$はどこかに同じ値を持つ$\mathrm{dp}[i]$があるはずなので，全ての$a_{j}$を同じ方法で更新して問題ないです．
# 略
メモ
単純に，①初項を決めて，②数列を前から順に見ていけば$O(n^{2})$でできるのでは？分割数
【入力】4
3
10000
【出力】
4
【コード】
n = int(input()) m = int(input()) M = int(input()) dp = [['']*(n+1) for _ in range(m+1)] dp[1][1:] = [1]*n for i in range(2, m+1): for j in range(1, n+1): if i < j: dp[i][j] = dp[i-1][j] + dp[i][j-i] elif i==j: dp[i][j] = dp[i-1][j] + 1 else: dp[i][j] = dp[i-1][j] print(dp[m][n]%M)
【ポイント】
DPを
- $\mathrm{dp}[i][j]=j$を$i$以下に分割する方法の数
漸化式を作りたいので，$i$が一つ小さい場合を考えると
- $\mathrm{dp}[i][j]=$「$\mathrm{dp}[i-1][j]$ ($j$を$i-1$以下に分割する方法の数)」＋「$j$を$i$ぴったりに分割する方法の数」
ここで，「$j$を$i$ぴったりに分割する方法」は$i > j$なら0，$i=j$なら1です．$i < j$の場合は，各分割に一つ以上の要素が含まれるので，
- はじめに各分割に一つづつ割り当てる，$i$個を確保しておき，
- 残る$j-i$個を$i$以下に分割する（上の各分割に加える）
以上より，漸化式
\mathrm{dp}[i][j]
=
\begin{cases}
\, \mathrm{dp}[i-1][j] + \mathrm{dp}[i][j-i] & (i < j) \\
\, \mathrm{dp}[i-1][j] + 1 & (i=j) \\
\, \mathrm{dp}[i-1][j] & (i > j)
\end{cases}
\end{aligned}
初期値は，漸化式が参照している添字から，$i=1$の場合に全ての$j$に対して与えればよく
\mathrm{dp}[1][j]=1
\end{aligned}
本の説明
書籍中で数行で説明されている内容を詳細に説明します．集合
S=\bigl\{ \{a_{k}\}_{k=1}^{i} \,\bigl |\, \sum_{k=1}^{i} a_{k}=j, a_{k}\geq 0, i=1,…,j \bigr\}
\end{aligned}
S_{1}&=\bigl\{ \{a_{k}\}_{k=1}^{i} \,\bigl |\, \sum_{k=1}^{i} a_{k}=j, a_{k}\textcolor{red}{ > } 0, i=1,…,j \bigr\} \\
S_{2}&=\bigl\{ \{a_{k}\}_{k=1}^{i} \,\bigl |\, \sum_{k=1}^{i} a_{k}=j, a_{k}\geq 0, i=1,…,j ,\textcolor{red}{\text{少なくとも1つ$a_{k}=0$となるものが存在}}\bigr\} \\
&=\bigl\{ \{a_{k}\}_{k=1}^{\textcolor{red}{i-1}} \,\bigl |\, \sum_{k=1}^{\textcolor{red}{i-1}} a_{k}=j, a_{k}\geq 0, \textcolor{red}{i-1}=1,…,j \bigr\}
\end{aligned}
|S|=|S_{1}| + |S_{2}|
\end{aligned}
$S$と同じ形の集合$S_{3}$で，$|S|$と要素数が同じものをつくります．具体的には
S_{3}&=\bigl\{ \{a_{k}-1\}_{k=1}^{i} \,\bigl |\, \sum_{k=1}^{i} (a_{k}-1)=j-i, a_{k}-1\geq 0, i=1,…,j \bigr\}
\end{aligned}
以上より，漸化式
\mathrm{dp}[i][j]
=\mathrm{dp}[i][j-i] + \mathrm{dp}[i-1][j]
\end{aligned}
重複組合せ
【入力】3
3
1 2 3
10000
【出力】
6
【コード】
n = int(input()) m = int(input()) a = list(map(int, input().split())) M = int(input()) dp = [['']*(m+1) for _ in range(n+1)] for j in range(1, m+1): if j <= a[0]: dp[1][j] = 1 else: dp[1][j] = 0 for i in range(1, n): for j in range(1, m+1): if j == 1: dp[i+1][j] = i + 1 elif 1 < j and j < a[i]+1: dp[i+1][j] = dp[i][j] + dp[i+1][j-1] elif j == a[i]+1: dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - 1 else: dp[i+1][j] = dp[i][j] + dp[i+1][j-1] - dp[i+1][j-a[i]-1] print(dp[n][m]%M)
【ポイント】
DPを
- $\mathrm{dp}[i+1][j]=i$番目までの品物から$j$個選ぶ組み合わせの数
漸化式を得るため，「分割数」の場合と同じように，一つ小さい$i$を考えると
- $\mathrm{dp}[i+1][j]=$「$\mathrm{dp}[i][j]$ ($i$番目を含まない方法の数)」＋「$i$番目を含む方法の数」
右辺の第2項を考えます．$i$番目の1つを確保して残り$j-1$個を自由に選ぶ方法を求めればよいです．$\mathrm{dp}[i+1][j-1]$は$i$番目の上限が$a_{i}$の場合の組み合わせの数です（後述するように$j > a_{i}+1$の場合）．今欲しいのは，上限が$a_{i}-1$の計算結果なので，$\mathrm{dp}[i+1][j-1]$から$i$番目が$a_{i}$個含まれている組み合わせの数を除けば良いことになります．これは，$i$番目をさらに$a_{i}$個追加で確保した残り$j-(a_{i}+1)$個を$i$番目までで自由に選ぶ方法$\mathrm{dp}[i][j-(a_{i}+1)]$で求められます．
ここまで，配列の添字がゼロ以下になる部分は考えていませんでした．$j=1$の場合は$\mathrm{dp}[i+1][1]=i+1$です．$j < a_{i}+1$の場合は$\mathrm{dp}[i+1][j-1]$が上限$a_{i}$でも$a_{i}-1$でも同じ値となるので，最後の引き算が不要になります．$j=a_{i}+1$の場合は，$\mathrm{dp}[i+1][j-1]=\mathrm{dp}[i+1][a_{i}]$で，$i$番目が$a_{i}$個含まれている組み合わせの数は$1$になります．
以上より，漸化式
&\mathrm{dp}[i+1][j] \\
&=
\begin{cases}
\, i+1 & (j=1) \\
\, \mathrm{dp}[i][j] + \mathrm{dp}[i+1][j-1] & (1 < j < a_{i}+1) \\
\, \mathrm{dp}[i][j]
+\mathrm{dp}[i+1][j-1]
-1 & (j = a_{i}+1) \\
\, \mathrm{dp}[i][j]
+\mathrm{dp}[i+1][j-1]
-\mathrm{dp}[i][j-(a_{i}+1)] & (a_{i}+1 < j) \\
\end{cases}
\end{aligned}
初期値は，漸化式が参照している添字から，
\mathrm{dp}[1][j]
&=
\begin{cases}
\, 1 & (j \leq a_{0}) \\
\, 0 & (a_{0} < j )
\end{cases}
\end{aligned}
