配る DP・もらう DP の特徴づけに関して - えびちゃんの日記

配る DP・もらう DP の特徴づけに関して - えびちゃんの日記

典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP...概要を表示 典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。 導入 主張 例 ナップサック問題 Eratosthenes の篩 回数の期待値・ゲームなど、操作を伴うもの 最短距離 所感 おわり 導入 初心者向けの解説の多くでは、ナップサック問題の DP などを例に出して、 for i in 0..n { for j in 0..=cap { dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]); } for j in 0..=cap - w[i] { dp[i + 1][j + w[i]] = dp[i + 1][j + w[i]].max(dp[i][j] + v[i]); } } で更新するのが配る DP で、 for