從記憶化搜索到遞推：

0-1背包

常見變形：

????1）至多裝capacity，求方案數(shù)/最大價值和

????2）恰好裝capacity，求方案數(shù)/最大/最小價值和

????3）至少裝capacity，求方案數(shù)/最小價值和

????另外，當?shù)玫揭粋€狀態(tài)轉(zhuǎn)移方程后（無論是不是背包問題），循環(huán)順序的考慮（正序或是逆序）是有跡可循的，如圖，如果 c 在某個位置，將 i, i+1 數(shù)組分稱 4 塊區(qū)域，那么如果是由左上和右下區(qū)域轉(zhuǎn)移而來，就是倒序；如果是右上和左下，則是正序：

最長公共子序列&編輯距離

最長遞增子序列

狀態(tài)機 DP

區(qū)間 DP