DP談義

ぱ @purple_jwl

DPといえばこの記事ですよね(?) d.hatena.ne.jp/Tayama/2011121…

not @not_522

あと、DPは「順番に辿れる」ってのが大事で、ループしてたりすると死ぬ

紙ぺーぱー @camypaper

とけるDP,とけないDPそんなのひとのかって

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

こどふぉの解説記事はあってないようなもの

しおしおた @shioshiota

tayamaさん is god

™ @tmaehara

状態遷移図を書いてパス分解してバッグサイズの最大値に状態を組化すれば任意の問題に対してDPが導出できますよ．

拙僧 @sessoh

例えば「テキトーに山の絵を描いてください」と言ったとき、山がどんなものか知っている「知識」と、思ったものを絵に描ける「技術」の他に、どんな風に描くかの「絵心」が必要なわけで、DPも、知識と技術の他に「DP心」が必要なのだ、と思う。

™ @tmaehara

ご覧ください！これが抽象化厨の末路です！

拙僧 @sessoh

自動で解こうとするとどうなるのか、考えていたので、とても勉強になった。

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

dpとgreedyの境界わかってない

hogeover30 @hogeover30

片足が沈む前にもう片方の足を前に出せば水の上を走れる的なアレ twitter.com/tmaehara/statu…

Odashi @odashi_t

厳密解を探さないDPがGreedy程度の認識

Shuichi Tamayose @_simanman

やっぱりDPは難しいじゃないか！(憤怒

拙僧 @sessoh

とても勉強になった（意味が分かったとは言ってない

みさわ @Mi_Sawa

ジャングル貪欲ガスベテ

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

@odashi_t それなら厳密解が求まらないdpというのも考えられるのでまずい気がする

Odashi @odashi_t

@takapt0226 式の上ではDPもGreedyも大差なくて、式の計算を途中であきらめるかどうか程度の違いじゃないかな…（式が問題の厳密解を求めるものとは言ってない）

not @not_522

誰か「全探索お姉さんでもわかる動的計画法」でLTやって

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

@odashi_t なるほど 状態空間を考えて、網羅するのがdp、しないのがgreedy

Odashi @odashi_t

@takapt0226 くらいに考えるのが幸せな気がする

Япон Бүресе🏴‍☠️ @southerwolfie

動的計画法の問題の解説はたいてい「DPするだけ」とか「これはDPで求められる」だと思う。親切だと何でDPするか教えてくれるけどこれは複雑な漸化式のときだけ。

大堀龍一 (Ryuichi OHORI) @__DaLong

動的計画法の問題だったかどうか覚えてないけど、りんごさんの生解説で、第一声が「入力が x のときの答えを f(x) とおくと」だったときはわかりやすくて感動した。

Dは堕天のD @Darsein

全探索お姉さんはアルゴリズム力が上がってもスケールしないサイズのインスタンスに挑戦し続けるだけだから

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

いつの間にか"["と"]"というファイルができていた(vim...

™ @tmaehara

dl.acm.org/citation.cfm?i… このあたりが参考文献です