写在最前面，在写第七章之前，我以前在上算法课的时候也总结过一篇关于动态规划的文章，这次的总结也算是复习+学习新知，侧重点变成了算题。动态规划很多时候需要的是一种思想，一种能察觉到问题具有最优子结构，然后通过分析得到递推关系式的过程。而很多问题的最优子结构性质如果是刚接触过一般难以在短时间内解决，所有还是鼓励平时多算题，多积累，说不定哪天考场上就出现了你碰过的题目了呢，

首先关于背包问题的整理和相关的详细代码请见我的github

跳台阶[推导，得到类似于斐波那契的递推关系式] 不容易系列之一（九度教程第 94 题） 需要通过数学推导得到错排公式

对于LIS问题可以得到如下递推公式： F [ i ] ={max⁡1 ≤ j < i F[j]+1,aj<aimax⁡1 ≤ j < i F[j],aj≥aiF[i] = \begin{cases} \max \limits_{1≤j<i}{F[j]+1}, &a_j<a_i \\ \max \limits_{1≤j<i}{F[j]}, &a_j≥a_i \end{cases}F[i]=⎩⎨⎧​1≤j