从记忆化搜索到递推：

0-1背包

常见变形：

    1）至多装capacity，求方案数/最大价值和

    2）恰好装capacity，求方案数/最大/最小价值和

    3）至少装capacity，求方案数/最小价值和

    另外，当得到一个状态转移方程后（无论是不是背包问题），循环顺序的考虑（正序或是逆序）是有迹可循的，如图，如果 c 在某个位置，将 i, i+1 数组分称 4 块区域，那么如果是由左上和右下区域转移而来，就是倒序；如果是右上和左下，则是正序：

最长公共子序列&编辑距离

最长递增子序列

状态机 DP

区间 DP