概念

最优子结构

对于多阶段决策问题，如果每一个阶段的最优决策序列的子序列也是最优的，且决策序列具有“无后效性”，就可以将此决策方法理解为最优子结构。

第二数学归纳法

第二数学归纳法原理是设有一个与正整数n有关的命题，如果：
（1）当n=1，2时，命题成立；
（2）假设当n≤k（k∈N）时，命题成立，由此可推得当n=k+1时，命题也成立。
那么根据①②可得，命题对于一切正整数n来说都成立。

最长递(递减)序列

从一边开始，将端点确定为最优解，再向另一端刷新，类似第二数学归纳法。

和时间有关的dp

时间可逆，可以考虑从后向前dp

背包问题

背包问题指一类各个事件之间相互独立，每种事件有不同的状态可以选择，按照事件的状态dp。
有01背包，完全背包，有限背包，有依赖背包，树形背包等。
参考背包问题