Dynamorphism 概論
1. はじめに1.1. まえがき この記事では、関数型プログラミングにおいて動的計画法(Dynamic Programming)を行う手法の一つである dynamorphism について解説します。 しかし、dynamorphism という概念はそれ単体で説明できるものではなく、F-代数 や catamorphism, anamorphism, hylomorphism, histmorphism などの各種概念を用いないと説明できないものです。そこでこの記事では順々とそれらの概念を追っていき、最後にdynamorphismに行き着くような構成になっています。 そのため、この記事は dynamorphism の説明記事であると同時に、F-(余)代数や catamorphism, anamorphism 等に関する解説記事でもあります。 ここで留意していただきたい点が何点かあります。いわゆる
なぜｄｐ「やるだけ」なのか ～動的計画法について考える その１～ - kuuso1のブログ
これは、Competitive Programming Advent Calendar 2016の17日目の記事です。 競技プログラミング（以下，競プロ）においてよく出題される動的計画法（Dynamic programming，通称dp）について，「dpやるだけ」という表現を稀に見かけます．競プロを始めた人のうち，多くの人が（少なくとも自分にとっては）最初の壁のうちの一つと言ってもいいdpというジャンルがなぜ「やるだけ」などというパワーワードを伴ってしまうのか．今回はそういうところから，ふわっと動的計画法について考えてみようと思います．どちらかといえばテクニック的な内容というよりは自分がdpの問題に触れるときに意識しているようなことを書いているだけなので，参考になったりならなかったりすると思いますがご容赦のほど． 動的計画法とは 動的計画法 wikipedia によると「対象となる問題を複
『ナップサック問題 個数制限なし 自分用メモ』
i番目の物の重さがw(i) 価値がv(i)とする。 i番目までで重さjまででの最大になるように選んだ時の合計価値をdp[i][j]とする。 dp[i+1][j]はi+1番目をいくつか使った時と全く使わない時のうちの最大値なのでkを１以上でj-k*wが0以上を満たす自然数として dp[i+1][j]=max( dp[i][j], dp[i][j-k*w(i+1)]+k*v(i+1) ) ここで実は dp[i+1][j-w(i+1)]=max( dp[i][j-w(i+1)] , dp[i][j-w(i+1)-q*w(i+1)]+q*v(i+1) ) である。ここで右辺に既視感があることに気づく。（dp[i+1][j-w(i+1)]は第一式の右辺の dp[i][j-k*w(i+1)]+k*v(i+1)よりv(i+1)小さいのと同じじゃん） つまり第一式のmax( dp[i][j-k*w(i+1
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、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 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
