算法学习 - 动态规划 Dynamic Programming

一.什么是动态规划？

---

我们先来看一下wiki上面对于动态规划的定义：

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

就是说，动态规划是一种方法，用于解决复杂问题时将复杂问题转化为一个个相似的小问题，所有的问题都只需要计算一次，并且储存它们的解。

很多人学完动态规划后，常常不知所用，不知道该在什么样的情况下面用到动态规划，或者可以说，根本不了解动态规划这个方法的意义所在。所以我们可以在各个平台上面看到对动态规划的人生三问：什么是动态规划？为什么要用动态规划？动态规划的意义是什么？动态规划要往哪里去？

为什么很多人学完动态规划后都有这样的困惑呢？因为刚刚Wiki上面的解释已经很清楚了，动态规划是一种方法，动态规划并不是一种一成不变的算法。

有些算法，比如DFS、BFS算法，你甚至只需要去理解以后记住这个算法的模板，怎么去用，在哪些情况下用，以后遇到类似的问题，将模板转化一下就可以用了。但动态规划不是，这就是动态规划的迷雾所在，有些题你在看了题解以后发现这道题居然能够用动态规划的思路去做，你不禁感叹：动态规划真是好东西...

按照我个人的理解来说，动态规划就是

动态规划就是一种将一个大问题分解为各个独立的小问题，建立一个可保存数据的结构（通常是数组）来缓存小问题已经得出的结果，并且在后面通过一个归纳的方程（即状态转移方程）复用这个结果，得出大问题的结果的一种方法。

如果觉得这段话很绕也没事，注意几个关键字 " 缓存数据 复用数据 状态 转移方程 方法 " ，这些就是动态规划的要义所在。

我再来举一个我在网上看到的一个比较幽默的例子吧，也很好的说明了什么是动态规划

Q：（1+1+1+1+1+1+1+1+1+1+1） = ?

A：（你一个一个数了，很慢的回答）等于11

Q：（1+1+1+1+1+1+1+1+1+1+1）+1=？

A：（你只看到右边多了个+1，快速回答了）等于12

为什么第二次你不需要一个一个数到底有多少个“1”在等式左边呢？因为第一次问你的时候，你数了，知道等于11。第二次在左边加了个1，对于你来讲，就是问你：11+1=？ 于是你几乎不需要停留，脱口而出：“12”。（恭喜你，达到了小学一年级的水平）

回到正题，这个例子其实就是在阐述缓存数据（缓存了前面的11）、复用数据（用到了前面缓存的11）、转移方程（在这个例子里就是呈现的算术）这些动态规划的核心。

二.什么问题能用到动态规划？

什么情况下能用到动态规划？

就是满足最优子结构、无后效性的时候。

浅显的说，一个问题如果大问题(原问题）能够分解为一个个小问题，小问题可以拆分为更小的问题，同时，大问题的最优解能够通过小问题的最优解递推得到、小问题的答案可以由更小的问题的最优解递推得到（这个大与小指规模的大小），这就是满足“最优子结构”的问题。

在这里大问题的结果，我们只看小问题的答案，而不用考虑小问题的答案是如何得到的，这就是满足“无后效性”的问题。即

“现在就是过去的总结，现在决定未来，未来与过去无关。”

那么这个问题就能够通过动态规划的思想来解决。

现在不理解这两个术语意思没事，后面根据一些例子大概就能很好的了解了。

其实说“什么问题能用动态规划”并不是很恰当，我们应该这样说“什么问题适合用动态规划来更轻松的解决？”

那就是小问题的答案长期被复用。

复用，这个熟悉的词汇又出现了，长期被复用，这才是关键。

如果不被长期复用，那么除去“缓存、复用”的步骤，这个“定义”依然是可以适用于其他情况的。

因为从哲学来说，实际上大问题都是可以转化为小问题的。那为什么我们一定要用动态规划呢？我们用递归从上到下暴力求解不也可以吗？还减少了“找状态转移方程”这个麻烦的过程，我们直接把数据交给计算机，叫计算机一个一个遍历然后从中筛选取得我们想要的值就行了，要知道计算机最擅长的就是计算，计算机最不怕的就是大量的数据。

一切的一切，在于长期被复用。

多次被复用，那么用一个结构储存当前的结果，以便于后续使用，这才是对我们，对计算机最善良的做法。

在这里举一个Fibonacci数列的例子，更好的理解长期被复用带来的影响。

Fibonacci数列的转移方程是：F(n)=F(n-1)+F(n-2)

你要求F(100)，自然要知道F(99),F(98)。

你要求F(99)，自然要知道F(98),F(97).

你要求F(98)，自然要知道F(97),F(96).

...

Fibonacci数列在学校基本都是用来讲递归使用的，但是你仔细思考一下，Fibonacci数列用递归方法这样轮下去，你会发现你调用了很多很多很多步骤去重复求一个已经求出来的值。

所以我们重新思考一下：

• 1.Fibonacci数列满足最优子结构吗？答案很明显，Fibonacci数列问题就是一个大问题拆解成小问题，小问题再拆解成小小问题来解决的.

• 2.Fibonacci数列满足无后效性吗？答案也是很明显的，Fibonacci数列很明显也只需要用到N-1和N-2的数值即可.

递归方法，你要从F(99)求到F(1)，然后再从F(98)求到F(1)，你才能得到F（100）

动态规划，我们第一次求到F（99）的时候直接保存值（很明显，每一个值在Fibonacci数列里面都会调用多次），后期用到直接拿来用，省下的时间复杂度是指数级别，不是一点半点。

三.动态规划思路

1.明确题目里的状态

2.明确DP数组的定义

3.做出正确的状态转移方程。

在Fibonacci数列问题里面，我们要求的是指定数字的Fibonacci值

状态自然就是数字n，

我们把F（n）定义为：数字为n时的Fibonacci值

那么根据我们的状态定义，该题正确的状态转移方程是 F(n)=F(n-1)+F(n-2)

每一次求出F（n），我们就把这个值保存起来，实现了缓存数据并复用。

以上任何一个环节定义错误，都会影响到下一环节的进行，这就要求我们明确状态、明确DP数组的定义，不然转移方程有可能会不再适用（也就是脱离了“最优子结构”或脱离了“无后效性”），也就自然得出了错误的最终结果。

这种情况下，我们要重新考虑状态、重新考虑DP数组的定义。确保DP状态的定义满足：

• 1.最优子结构
• 2.无后效性

通过几个题目，我本人的一般处理思路是：

1.思考状态是否找对、找全？下一结果不能由当前结果递推得到（也就是说，当前的DP状态定义不满足“最优子结构”），有可能是状态不够，也许这个DP数组可以升为二维、三维甚至更多维来解决（参考 Leetcode.买卖股票问题）、或者可能要用到两个、多个状态定义来做（参考 Leetcode.乘积最大子数组）用到来储存更多状态.

状态越明确，范围越明确，从而可以从更多的状态（更为明确的范围）里面做出正确的选择，找出正确的状态转移方程。

2.思考DP数组的定义是否正确？DP[i]储存的东西是什么？变换一下思路，定义正确的DP数组，充分仔细考虑问题条件与所求，确保储存的东西一经确定，不会受到未来（过去）的影响。（参考最长子数组和问题）

为什么一定要保证状态的定义满足最优子结构、无后效性？

上面已经写了，DP数组定义不适当的话，不仅找不到合适的状态转移方程，而且在做题过程中可能会混乱状态，不知所然。

拿 最长子数组和 的问题来举例.

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

如果你做了一些其他求最值的动态规划的题目，不按步骤一一考虑，按所谓“经验”，胡乱的你可能就这样定义F[i]了：前i个数字里面的最大子数组和，结果输出F[len(nums)-1]就行了。

看起来似乎没毛病，但当你按这个定义时，状态转移方程怎么找？

举个例子，nums = [4,-1,5] 这个数组，当你一开始选了4的时候，max更新为4，由于下一个是-1，4-1=3，比之前的小了，于是你放弃了选择-1，放弃了继续连续，于是你重新开始，选了[3]，max = 5。这就是鼠目寸光，如果你继续选，max是可以达到4-1+5=8的。

于是，我们应该这样定义F(n)：以n为右端点的子数组的最大和。

于是，以每一个数字为右端点的子数组和就都有了，然后我们再考虑后面的结果加不加这个值，这样就会避免再出现之前鼠目寸光的情况，最后从所有的F（n）中选出最大值，也就是以n为右端点的子数组的最大值就是最长子数组和的大小。

所以这道题目的状态转移方程为： \[ F(i) = max(nums[i],nums[i]+F(i-1)) | i\ \le n \] 关键就在于，这个问题问的是数组和。要么连续，要么重新开始、割舍一切。所以，最大值不一定是F(end）,我们应该从F（1..end)里面寻找最大值，即为我们要求的最大子数组和。

该题的Python解法代码如下：

 
nums = [0]+[-2,1,-3,4,-1,2,1,-5,4]
n = len(nums)
dp=[0]*n
for i in range(1,n):
    dp[i] = max(nums[i],nums[i]+dp[i-1])
res = 0
for i in range(n):
    res = max(res,dp[i]);
 
print(res)