1初识动态规划

这节课的内容不涉及动态规划的理论，而是通过两个例子：0-1背包问题、0-1背包问题升级版，展示了动态规划是如何解决问题的。这两个例子都是非常经典的动态规划问题，只要真正搞懂它们，基本上动态规划已经入门一半了。

从例子中我们可以发现，大部分动态规划能解决的问题，都可以通过回溯法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是动态规划的空间复杂度也提高了，所以很多时候，我们会说动态规划是一种空间换时间的算法思想。

2动态规划理论

什么样的问题适合用动态规划解决呢？这些问题可以总结概括为“一个模型三个特征”。其中，“一个模型”指的是，问题可以抽象成分阶段决策最优解模型。“三个特征”指的是最优子节、无后效性和重复性子问题。

动态规划的解题思路有两种，分别是状态转移表法和状态转移方程法。其中，状态转移表法解题思路大致可以概括为，回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。状态转移方程法的大致思路可以概括为，找最优子结构-写状态转移方程-将状态转移方程翻译成代码。

对比之前讲过的四种算法思想，贪心、回溯、动态规划可以解决的问题模型类似，都可以抽象成多阶段决策最优解模型。尽管分治算法也能解决最优问题，但是大部分问题的背景都不适合抽象成多阶段决策模型。