典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita なんかややこしい。。 全部愚直に一から毎回計算すると大変なやつを、ところどころ覚えておいて表にでもしておけば、計算量減らせるやん的な雰囲気を醸し出しているやつ…