精读

 

动态规划不是魔法，它也是通过暴力方法尝试答案，只是方式更加 “聪明”，使得实际上时间复杂度并不高。

 

动态规划与暴力、回溯算法的区别

 

上面这句话也说明了，所有动态规划问题都能通过暴力方法解决！是的，所有最优解问题都可以通过暴力方法尝试（以及回溯算法），最终找出最优的那个。

 

暴力算法几乎可以解决一切问题。回溯算法的特点是，通过暴力尝试不同分支，最终选择结果最优的线路。

 

而动态规划也有分支概念，但不用把每条分支尝试到终点，而是在走到分叉路口时，可以直接根据前面各分支的表现，直接推导出下一步的最优解！然而无论是直接推导，还是前面各分支判断，都是有条件的。动态规划可解问题需同时满足以下三个特点：

 

存在最优子结构。

 

存在重复子问题。

 

无后效性。

 

存在最优子结构

 

即子问题的最优解可以推导出全局最优解。

 

什么是子问题？比如寻路算法中，走完前几步就是相对于走完全程的子问题，必须保证走完全程的最短路径可以通过走完前几步推导出来，才可以用动态规划。

 

不要小看这第一条，动态规划就难在这里，你到底如何将最优子结构与全局最优解建立上关系？

 

对于爬楼梯问题，由于每层台阶都是由前面台阶爬上来的，因此必然存在一个线性关系推导。

 

如果变成二维平面寻路呢？那么就升级为二维问题，存在两个变量 i,j 与上一步之间关系了。

 

如果是背包问题，同时存在物品数量 i、物品重量 j 和物品质量 k 三个变量呢？那就升级为三位问题，需要寻找三个之间的关系。

 

依此类推，复杂度可以上升到 N 维，维度越高思考的复杂度就越高，空间复杂度就越需要优化。

 

存在重复子问题

 

即同一个子问题在不同场景下存在重复计算。

 

比如寻路算法中，同样两条路线的计算中，有一段路线是公共的，是计算的必经之路，那么只算一次就好了，当计算下一条路时，遇到这个子路，直接拿第一次计算的缓存即可。典型例子是斐波那契数列，对于 f(3) 与 f(4)，都要计算 f(1) 与 f(2)，因为 f(3) = f(2) + f(1)，而 f(4) = f(3) + f(2) = f(2) + f(1) + f(2)。

 

这个是动态规划与暴力解法的关键区别，动态规划之所以性能高，是因为 不会对重复子问题进行重复计算，算法上一般通过缓存计算结果或者自底向上迭代的方式解决，但核心是这个场景要存在重复子问题。

 

当你觉得暴力解法可能很傻，存在大量重复计算时，就要想想是哪里存在重复子问题，是否可以用动态规划解决了。

 

无后效性

 

即前面的选择不会影响后面的游戏规则。

 

寻路算法中，不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联，没有选择一说，所以也不存在后效性问题。

 

什么场景存在后效性呢？比如你的人生是否能通过动态规划求最优解？其实是不行的，因为你今天的选择可能影响未来人生轨迹，比如你选择了计算机这个职业，会直接影响到工作的领域，接触到的人，后面的人生路线因此就完全变了，所以根本无法与选择了土木工程的你进行比较，因为人生赛道都变了。

 

有同学可能觉得这样局限是不是很大？其实不然，无后效性的问题仍然很多，比如背包放哪件物品、当前走哪条路线、用了哪些零钱，都不会影响整个背包大小、整张地图的地形、以及你最重要付款的金额。

 

解法套路 - 状态转移方程

 

解决动态规划问题的核心就是写出状态转移方程，所谓状态转移，即通过某些之前步骤推导出未来步骤。

 

状态转移方程一般写为 dp(i) = 一系列 dp(j) 的计算，其中 j < i。

 

其中 i 与 dp(i) 的含义很重要，一般 dp(i) 直接代表题目的答案，i 就有技巧了。比如斐波那契数列，dp(i) 表示的答案就是最终结果，i 表示下标，由于斐波那契数列直接把状态转移方程告诉你了 f(x) = f(x-1) + f(x-2)，那么根本连推导都不必了。

 

对于复杂问题，难在如何定义 i 的含义，以及下一步状态如何通过之前状态推导。 这个做多了题目就有体会，如果没有，那即便再如何解释也难以说明，所以后面还是直接看例子吧。

 

先举一个最简单的动态规划例子 - 爬楼梯来说明问题。

 

爬楼梯问题

 

爬楼梯是一道简单题，题目如下：

 

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？（给定 n 是一个正整数）

 

首先 dp(i) 就是问题的答案（解法套路，dp(i) 大部分情况就是答案，这样解题思路会最简化），即爬到第 i 阶台阶的方法数量，那么 i 自然就是要爬到第几阶台阶。

 

我们首先看是否存在 最优子结构？因为只能往上爬，所以第 i 阶台阶有几种爬方完全取决于前面有几种爬方，而一次只能爬 1 或 2 个台阶，所以第 i 阶台阶只可能从第 i-1 或 i-2 个台阶爬上来的，所以第 i 个台阶的爬法就是 i-1 与 i-2 总爬法之和。所以显然有最优子结构，连状态转移方程都呼之欲出了。

 

再看是否存在 存在重复子问题，其实爬楼梯和斐波那契数列类似，最终的状态转移方程是一样的，所以显然存在重复子问题。当然直观来看也容易分析出，10 阶台阶的爬法包含了 8、9 阶的爬法，而 9 阶台阶爬法包含了 8 阶的，所以存在重复子问题。

 

最后看是否 无后效性？由于前面选择一次爬 1 个或 2 个台阶并不会影响总台阶数，也不会影响你下一次能爬的台阶数，所以无后效性。如果你爬了 2 个台阶，因为太累，下次只能爬 1 个台阶，就属于有后效性了。或者只要你一共爬了 3 次 2 阶，就会因为太累而放弃爬楼梯，直接下楼休息，那么问题提前结束，也属于有后效性。