動的計画法を学ぶ
動的計画法とは
再帰で表現したものを下から計算することで
計算の重複をなくすことが目的。
再帰で解けるけど、計算量がやばいから動的計画法にしよう
っていう発想
だから、僕が問題を解く上では
動的計画法を意識せず、普段どおり再帰で解く。
計算量が指数時間になってしまったら動的計画法を導入する。
www.slideshare.net
上のスライドシェアを見て、動的計画法について思ったこと
・過程は重要ではない
引数にaccを使うべきでない
再帰を考える段階で、終了条件が引数に現れるようにする必要がある
(acc.sum == 15 だったら終了とかはダメ、再帰の段階で sum-val を渡すなどに変更する)
・再帰だと木で考えるが、動的計画法が表で考える
再帰を動的計画法に直す際は、このイメージ持っておくと良さそう
木のままだとイメージが難しい。
表にすれば、前のがわかれば、次がわかるがイメージしやすそう。
動的計画法（Dynamic Programming）をサルでも分かるように説明する - その１（フィボナッチ数列） - ベルリンのITスタートアップで働くソフトウェアエンジニアのブログ
これも動的計画法のイメージがわかりやすかった。
追記 抱いた疑問
最長増加部分列を求める問題について
この問題って動的計画法を使わずに解ける？
これを解くアルゴリズムはどれも動的計画法を使っている。
自分の手で解くとしても動的計画法的な解き方をする。
上の方では普通に解けるものを高速化するのが動的計画法って理解したけど
この問題に関しては解き方の段階から動的計画法で考えているような気がする。
