動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
典型的な 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 =
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
