DP談義

向日葵 @pappagukun

動的計画法で検索してWikipediaの次に出てくるの診断人さんのページだ… すごい方なんだなあ〜

nico_shindannin（診断人） @nico_shindannin

（まず、じじいシャワーシーンを想像させて、朝からみんなに全体ダメージ！）

nico_shindannin（診断人） @nico_shindannin

去年わしの動的計画法のやつ、「動的計画法自体は理解できたけど、自力で解くのはムリ、TopCoderの緑上位～青下位」を読者と想定して書いたので、動的計画法の説明はほぼ書いてないです…。ただ、リンクを貼った記事２つiwiさんとchokudaiさんのは初心者にもお勧めできます！

nico_shindannin（診断人） @nico_shindannin

プログラミングコンテストでの動的計画法 by @iwiwi slideshare.net/iwiwi/ss-35785… @SlideShareさんから

nico_shindannin（診断人） @nico_shindannin

最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ itmedia.co.jp/enterprise/art…

Masaki Hara @qnighy

動的計画法について一般的な説明を試みようとすると闇に呑まれる、具体的な問題ごとに説明をするしかない

Masaki Hara @qnighy

1,2問程度、動的計画法と呼ばれている問題を読み、1時間考えてわからなかったら答えを見て(教えてもらって)、そのあとで自力で実装する ってやればだいたいわかるんじゃない？ DPの問題なんてたくさんあるだろうし

agw @masashinakata

@nico_shindannin 僕診断人さんの記事かなり好きですよー。定期的に読み返したりします

拙僧 @sessoh

そもそも、「DPが分からない」というより「DPなのかどうかも分からない」「どうすればDPになるのか分からない」だろうから、DPの解き方そのもののよりも、そこに至る考え方を育成する診断人さんの記事があるわけですな。

Masaki Hara @qnighy

「答えを見て、そのあとで自力で実装する」は重要な練習方法だよ。 実装することで身につくものは多い

拙僧 @sessoh

自分で書かないと、分かった気がしただけで終わるよね。

nico_shindannin（診断人） @nico_shindannin

@masashinakata ありがとうございます！

nico_shindannin（診断人） @nico_shindannin

そもそも、わし自身が動的計画法が苦手なので、他の得意な人のツイートをRTしていくのじゃ。

hogeover30 @hogeover30

動的計画法の問題の解説いつものパターン 「 dp[...]...[...] とおくと、…」 ← どこから出てきたんだ？まあ慣れれば思いつけるようになるんだろう 「 こう書けます」 ← なんで？？？？？？？？？？

ぷち＠プログラマ日本一です @takapt0226

動的計画法自体の解説を読んでも余計いみわからんくなるだけな気がする

nico_shindannin（診断人） @nico_shindannin

いま、動的計画法の正解率をみたら、3%から10%まで上がってた！これはうれしいのじゃ。 otinn.com/topcoder/al/pr…

拙僧 @sessoh

数学の問題で、突然謎の補助式が出てくるようなものか。

ぱ @purple_jwl

動的計画法、昔はホント意味不明で全く解けなかったけど今は少しだけなら解けるし慣れって大事。

ぷち＠プログラマ日本一です @takapt0226

dpはマジで慣れるしかないって感じだ

紙ぺーぱー @camypaper

@purple_jwl 動的計画法何回も解いてると、なんかこんな感じでしょみたいので解けますよね

ぷち＠プログラマ日本一です @takapt0226

01ナップザックのdpを初見ですんなり理解できたらすごい

拙僧 @sessoh

結局、解いてから帰納的に降りてくるものは、演繹的に考えても無理、というのが「動的計画法は難しい」の本質だろうか。 勝兵は先ず解きて而る後に解法を求む。

not @not_522

動的計画法は「状態」と「遷移」がわからないと何を言っているのか意味不明になる

‏velengel @dora_maruta

nico_shindannin's tweets and blogs are to my advantage.

nico_shindannin（診断人） @nico_shindannin

というわけで、出勤しまーす