Dynamic Programming

• Algorithms with Python / 欲張り法, 動的計画法

ヤバい。ヤバすぎる。あるNP問題を解くプログラムを今まで総当り方式で作ってたんだが、これを動的計画法使って書き直したらとんでもなく早くなった。具体的に言うと、1時間ほっといても答え出てこなかった問題が1秒かからず解ける感じ。3600倍のスピード。有り得ねー。パソコンとかない時代に動的計画法を思いついたRichard Bellmanは超偉い。かなり半端ない。オレは馬鹿だから解法を理解するのに数日かかったけど、これはやる価値あった。すげー。もうナップサック問題とか怖くねー。メモリ食うのが不安っちゃ不安だけどとりあえずそれは脇に置いておけ。あとやらなくちゃいけないレポートに手を付けないでプログラミングしてるオレも結構すげー。