エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる - わかばめにっき
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる - わかばめにっき
動的計画法(DP)について, qiita でまとめられました qiita.com 勉強になったのでメモ代わりに. やはり数... 動的計画法(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 =