きろく

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目のものまでで重さ j のときの価値の最大値 と定義する．このとき， dp(i, j) = max( dp(i - 1, j) , dp(i - 1, j - w_(i - 1)) + v_(i - 1) ) と漸化式が立つ．状態数 O(NW)，遷移 O(1) となり O(NW)． 解答 atcoder.jp メモ化再帰で書いたので少し実行時間とメモ…