DP談義

紙ぺーぱー @camypaper

@nico_shindannin いてらです！

しおしおた @shioshiota

状態という考え方が他の事柄でしたことあれば理解が早そう

nodchip@tanuki- @nodchip

自分の場合は動的計画法の問題が解けない場合は大抵状態のうまいもたせ方がわからないことが多い。

Dは堕天のD @Darsein

競プロやってないのに研究とかで動的計画法を使いこなしている人すごいなあと思う。僕は競プロやってなかったらDP使えてる気がしない

not @not_522

例えばグリットの最短経路数の場合、「どこにいるか」が状態で「どこから来るか」が遷移であることを見抜けば、dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]という式は自然と出てくる

nico_shindannin（診断人） @nico_shindannin

@camypaper いってきます！

hogeover30 @hogeover30

forループでは書けないけどメモ化再帰でなら解けるのは動的計画法できないと認めない

ぱ @purple_jwl

@camypaper ですね、でもやっぱり最初はつらかった記憶が('A`)

紙ぺーぱー @camypaper

@purple_jwl 最初は文字通り漸化式のやつとかしか僕も解けませんでしたね…(´･_･`)

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

ゲームスコア最適化系のdpは再帰じゃないと書けないなぁ

しおしおた @shioshiota

ダイクストラもそうだけど、状態が直感的だと理解しやすいよね（作られるグラフが、ノードがどの街にいるかで、道がエッジだと、直感的だと思う。

not @not_522

0-1ナップサック問題の場合、「何個目で重さがどれだけ」が状態になって「入れるか入れないか」が遷移になるので、dp[i+1][j]=max(dp[i][j],dp[i][j-w])になる

紙ぺーぱー @camypaper

DPは配る側しか書けないことに最近気づいた

not @not_522

DPの計算量は基本的にO(状態×遷移)になっていて、遷移のオーダーは簡単にわかることが多いので、うまい状態の持ち方を見つけるゲームになる

紙ぺーぱー @camypaper

DPの解けない問題はこの状態が見えないから解けないのがほとんどな気がする

ぱ @purple_jwl

DPって言うと音ゲーマーがざわつくので動的計画法と言っていきたい。

not @not_522

（遷移のオーダーを落とす有名問題もあります）

紙ぺーぱー @camypaper

あとは正しく状態を持たないとTLE,MLEする問題もあってその辺厄介すぎる

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

だよな〜 とにかくうまい状態を見つけることができれば勝利

hogeover30 @hogeover30

01ナップサック問題すらよくわからなくてもTシャツ貰えるしDPできない人はマラソンマッチをやろう

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

あぁ遷移のオーダー落とすのはむずいかも

‏velengel @dora_maruta

DPの解説見ると当然のように状況が噛み砕いて説明してあって、まずそこができないんだっつーのって毎回思う

ぱ @purple_jwl

@camypaper まあ今もDP解けないんですけどね、てへっ（つらい

™ @tmaehara

DPなんて貪欲の一種ですよ

紙ぺーぱー @camypaper

DPの解説記事は漸化式だけが解説に残されること多いんだけど、解けない人はその漸化式をどのように導出したのかに至る過程を含めて解説されないとわからないんだよなあ