蟻本 p.67
重複組み合わせの遷移式、下から4行目の所がなぜそうなるのかよく分からなかった
理解したーー。
$ O(nm^2)で考えてみる
大体の2次元DPに関しては「i番目までのooからxxがjの時の値」みたいなパターンが多い。なのでこのDPテーブルを手前から埋めていって、一番最後まで埋めきった時、dp[i][j]が答えになったりします（イメージです）。
今回の場合も、添字はdp[i][j] // i番目の品物の中から、j個を選ぶ組み合わせの数という風にします（テンプレ感）。
遷移を考えていくのですが、基本的には「今自分がいる所より手前側の値（既に埋まっている所）を使って作る」みたいな感じで遷移を考えていけばいいです。i=5を埋めていく時はi=4とかそれ以下から考えるみたいな感じです。
で、遷移を考えるコツとして「1手前の状態を考える」というのがあります。そう考えると、
「3番目までの品物から5個選ぶ組み合わせの個数」は、
2番目の時、既に5個選んでて、2番目を0つ取って5個
2番目の時、既に4個選んでて、2番目を1つ取って5個
2番目の時、既に3個選んでて、2番目を2つ取って5個
2番目の時、既に2個選んでて、2番目を3つ取って5個
2番目の時、既に1個選んでて、2番目を4つ取って5個
2番目の時、既に0個選んでて、2番目を5つ取って5個
くらいのパターンがあります。
問題を見ると、i番目の品物を取れるのは最大で$ a_{i}個までなので、あとはそこを考慮したらいい感じです。
dp[i+1][j]を埋めるには、dp[i][j]の総和を一回一回計算しないといけないので、計算量的には$ O(nm^2)になります。
https://gyazo.com/c429f4139c132c4e29a8df6849cf74aahttps://gyazo.com/913e3ccea2394f9e0ebc7202d45849cfこんな感じ
$ O(nm)にする
じつは先程の$ O(nm^2)は、工夫することで$ O(nm)になります。
先程の埋め方を見てみましょう。
https://gyazo.com/c429f4139c132c4e29a8df6849cf74aahttps://gyazo.com/913e3ccea2394f9e0ebc7202d45849cf
じつは、この求める操作は重複してしまっています。図を重ねてみると…
https://gyazo.com/f3b82af5299abc47c2d70f0850dce9c2
1,2,4の所から、赤と青の矢印が同時に出ています。この2つの求める計算の差分を取ると…
https://gyazo.com/ff8895a7f5dd2cabd7fb9ab4f8f49698
こうなります。10が既に求まっていれば、下を引いて上を足すだけで8を求めることができます。
3+4+2+1を4+2+1+1にするには3を引いて1を足せばいい、というアレです。
以上。