典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる - わかばめにっき動的計画法(DP)について, qiita でまとめられました qiita.com 勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は として書きます. ここで, は数列の要素数を表します. 1. 最大和問題 要素を持つ数列 から任意の個数の項を選んで和を取った時の最大値 def max_sum(N, a): dp = [0] * (N + 1) for i in range(N): dp[i + 1] = max(dp[i], dp[i] + a[i]) return dp[N] 2. ナップサック問題 重さと価値の情報を持つ 個の荷物を重さが 以下になるように詰め込むとき価値の和を最大化 def knapsack(N, W, weight, value): # 初期化 inf = float("inf") dp =
