小复习算法思想就是解题思路，是算法程序的提纲，常见的算法思想就4种： 贪心算法（Greedy Algorithm） 分治算法（Divide and Conquer） 动态规划（Dynamic Programming） 穷举搜索（Exhaustive Searching） 可以说90%以上的算法，都来自这4种基本思想。 贪心算法和分治算法回顾前面2节课，我们讲解了贪心算法和分治算法。 贪心算法是把原问题分解出几个部分，这几个部分一般是按时间先后或者任务先后划分，分别求出子问题最优解再合并在一起。也就是说将多个局部最优解生硬地合并在一起，就认为是全局最优解了。 而分治算法是将原问题的规模减小，变成更容易解决的问题，有时允许反复分治减规模减到很小，问题的最优解甚至达到一目了然的状态。 今天要讲的动态规划，简直是集上述两种思想之大成，又克服二者的缺点。 动态规划动态规划，英文是Dynamic Programming（DP），擅长解决“多阶段决策问题”，利用各个阶段之间的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题最优决策。 理解动态规划，可以先从名字入手。 “动态”，是指“变化的状态”，我们将怎样做决策这样的抽象问题，使用数据来定义为一个一个的状态，而这些状态是随着问题的规模而变化的。这里比较类似于分治法，问题的规模是变化的。 “规划”，英文是 programming，其实不是“编程”的意思，更易于理解的翻译应该是“表格”，也就是说，上面所说的那些“变化的状态”放在一些，成为一个表格，随着问题的推进，表格会不断地更新。  动态规划往往使用表格来存储中间结果 这就是动态规划。 从最简单的一个问题讲起动态规划是基础算法中最不好理解的，咱们先从一个最简单的小问题慢慢讲解。 问题：一个10级的台阶，每次只能上1级或2级，问题共有几种上法？ 读者可以先自己思考一下，这其实就是一类最简单的多阶段决策问题。 每一步上几级台阶，都是一个决策 其实，我们可以先把问题倒着想一下： 最后一次决策，也就是完成10级台阶的最后一步，要么是从第8级迈2级上来，要么就是从第9级迈1级上来的，所以也就是说，有多少种办法上8级，再加上有多少种办法上9级，就是完成10级台阶的方法总和。 如果用 F(n) 表示上n级台阶共有多少种方法，那么上面的推理表示为：
说到这里，我们发现： 1 将求F(10)这个问题，完美的分解成了F(9)和F(8)，找到了局部的最优解，与贪心算法有点像； 2 既然F(10)=F(9)+F(8)，那么F(9)=F(8)+F(7)，依此类推，最终问题被逐渐降低了规模，越来越简单，这又是分治的思想； 到这里我想大家对这个问题已经知道大概怎么做了，我们借助这个问题总结一下： 动态规划三要素
F(10)=F(9)+F(8)，就是F(10)问题的最优子问题，局部的贪心完美的将问题分解，如果得到的F(9)和F(8)都是最优解，那么F(10)一定是最优解。
分解到最后，一定是变成了规模最简单的问题，即F(1)和F(2)，这两个问题不能再分解了，不过没关系，他们很简单，心算就搞定了。
本问题的状态转移方程为：F(n)=F(n-1)+F(n-2)，这是解决问题的核心，是状态能够“动态”起来的原因。 其实还有一个重大问题问题到这里，看起来已经解决了，其实还有一个重大问题，大家看一下这个时间复杂度就知道了——  一个典型的二叉树结构 不得了啊，这才10级台阶，如果100级要算多长时间！ 不过仔细一看，就会发现，有好多中间结果是重复的！  相同颜色的部分其实是相同的结果 这就好办了，把计算过的中间结果都存起来呗，如果再次遇到计算过的问题，就直接去查询！ 这个存储中间结果的的表，叫做—— 备忘录。 真正的动态规划——思路再倒过来上面的算法很不错了，不过并不完全是动态规划的思路，我们需要将思路再倒过来： 从初始的边界条件F(1)和F(2)开始，使用状态转移方程，不就能更快地推导出结果么！  就是这么简单！ 每一个格子，其实就是一个状态，随着阶段的进行，这个状态格会不断更新，这就是动态规划。 跟分治法有什么区别？上面的例子，看起来有点像分治法啊，那么它们之间的区别在哪里？ 其实，动态规划最大的特点，在于状态转换方程中，子问题是“有重叠的”，这也是动态规划的意义所在，如果没有重叠，也就不存在上面所说的减小计算量的优势了，那么就退化成分治法了。 重复计算要努力避免 DP方程——动态规划算法的核心所以说，状态转换方程（DP方程）就是算法的核心，那么设计DP方程，有什么要注意的？
从上面的算法三要素中，可以看出，DP方程是从最优子问题中归纳而来的。 那么，什么才算“最优子问题”呢？ 就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前的基础上最优。具体的说，我们默认F(8)和F(9)就是最优的，在此基础上，得到最优的F(10)。 |
|
|
