https://twitter.com/kinaba のログ (twilog の方が便利です。)
| のどがいたい | |
| http://twitter.com/chokudai/status/10668611566 (via @chokudai)メモリが無限ならメモ⊇DPじゃないかな。制限があると http://topcoder.g.hatena.ne.jp/tanakh/20100121/1264024237 DPが必要。ProjectEulerでメモ化だとスタック溢れるのでDPにしたことが何度かあるけどどれだったっけ… | |
| #hijitsuzai ってハッシュタグ、 #hitsujikai って読んでなんで羊飼いなんだろうと思ってた… http://pcod.no-ip.org/yats/search?query=hitsujikai すでに先駆者が何人か | |
| そして完璧に風邪っぽい。ぬぬぬ | |
| @maeda ダイクストラ法はDPに分類されるものなのでしょうか。であれば、確かにメモ化では書きにくい例のように思います。 | |
| 『「ベルマンの最適性原理に従う問題をベルマン方程式で表現して、それを解く」という手法が狭義のDP』という感覚でいるので、他の原理（Dijkstra法の場合は距離の三角不等式）によって最適性を保証するアルゴリズムは、どこまでがDPなんだろう、という疑問を持ったのですが | |
| 問題構造が最適性原理に従ってて概ね解き方もそれに従ってれば、全部DPと呼ぶのがすっきりするのか。で、大きく分けるとトップダウンDP(いわゆるメモ化再帰)とボトムアップDP(いわゆる配列埋め)がありまして、最適性保証に他の条件を入れられる場合、どっちが書きやすいかは条件によります | |
| 三角不等式はおかしい。お前は何を言っているんだ http://twitter.com/kinaba/statuses/10717247554 | |
| あたまがまったく回らないのでさっさと寝て明日頑張ろう… | |
| @zakkas783 お気遣いありがとうございますー。そしてジンジャーティーのストックが切れた… |