動的計画法とは 再帰で表現したものを下から計算することで 計算の重複をなくすことが目的。再帰で解けるけど、計算量がやばいから動的計画法にしよう っていう発想だから、僕が問題を解く上では 動的計画法を意識せず、普段どおり再帰で解く。 計算量が指数…

再帰で解けるときは再帰でいい。下から積み上げていく解法のときに 動的計画法がぱっと使えるようになりたい。

螺旋本読んでもLISがわかんなかった。 以下のページがとてもわかり易かった。 最長増加部分列・最長共通部分列 [いかたこのたこつぼ]誤解してたこと ・Lは昇順に並んでいるから、これが最長増加部分列になると思ってた。 ・そうじゃなく、異なる長さの増加部…