読者です 読者をやめる 読者になる 読者になる

戻すDP

物体がN個あって何らかのDPをする時、dp[i+1]からdp[i]を復元できる時、復元することを戻すDPという.
いや、dp[i]からdp[i+1]を計算したんだからそんなことしても意味ないやろ、と思うかもしれないが、ちゃんと意味があって、"物体を使う順番が関係ない"場合,とりあえず普通にDPしてdp[N]を求めたあと,iをN番目の物体とみなすことで,"物体iを使わない場合"というのが簡単に求まる.
典型的なのが
D: 注文の多い高橋商店 - AtCoder Regular Contest 028 | AtCoder
これ.まず個数制限つきDPをやって,その後戻す.dp[i][j]=iまででj個使う とすると,
元の式が dp[i+1][j]=dp[i+1][j-1]-dp[i][j-1-A[i]]+dp[i][j] (ただしindexが0未満の値は0とみなす) (この式は遷移の図を書いてdp[i][j-1]とdp[i][j]の違いが2箇所しか無いことを見ればわかる)で、これを戻す形にすると、
dp[i][j]=dp[i+1][j]-dp[i][j-1]+dp[i][j-1-A[i]] となる.
よってdp2[i][j]=i以外でj個使う方法 とすると, dp2[i][j]=dp[N][j]-dp[N][j-1]+dp2[i][j-1-A[i]]となる.

重みがついてても同様にできる,と言うか本質部分は順番が関係ないことと復元ができることの二つだけ.
SRM663Medで重み付き+同じ重みでも区別が付く の個数制限付きDP + 戻す が出たけど,これでも出来る.(まあ実はいらないんだけど)