动态规划的试用前提
1. 无后效性
- 一旦f(i,j)确定，就不用关心如何计算f(i,j)
- 想要确定f(i,j)，只需要知道f(i-1,j)和f(i,j-1)的值。而至于他们如何计算出来，对当前或之后的任何子问题都没有影响
- 过去不依赖将来，将来不影响过去
2. 最优子结构
- f(i,j)定义就已蕴含了最优
- 大问题的最优解可以由若干个小问题的最优解推出。（max，min，sum...）
DP能适用的的问题：能将大问题拆解成几个小问题，且满足无后效性、最优子结构性质。
标签：无后效,套路,子结构,问题,最优,动态,规划 From： https://www.cnblogs.com/codingforum/p/17300752.html