動的計画法(DP)の基礎知識から例題、考え方、解説コードまで記載した個人的メモ
![響け!動的計画法 (DP) 入門〜個人的まとめ](https://cdn-ak-scissors.b.st-hatena.com/image/square/71aaa868b43ee0a1b2efd9cda89dd61ae6b05a8f/height=288;version=1;width=512/https%3A%2F%2Ffiles.speakerdeck.com%2Fpresentations%2Fe7f95192be0941839859936c54d4f03a%2Fslide_0.jpg%3F13622262)
この記事は、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 前編の図2つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メ
問題名:Common Subsequence (PKU) 出典:Southeastern Europe 2003 難易度:☆☆☆ 問題の種類:DP 解法:LCS (Longest Common Subsequence) 解答ソースコード: 1458-deq.cpp アルゴリズムの概略 DPの四天王(?),LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など,通常はこれをひねった問題が出てきます。 LCSとは,二つの値の列(この問題では文字列)が与えられて,最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが,順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが,この問題ではその長
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く