从斐波那契数列开始讲解何为动态规划算法

vlambda
2020-05-07

从斐波那契数列开始讲解何为动态规划算法

首先我们来看下动态规划的百度百科的定义：

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作

从定义中可知一般动态规划算法的一般形式是求最值，比如说：300.最长上升子序列、72.编辑距离（最小）以及今天的每日一题的 53.最大子序和。

在一般的最值问题中我们都有一种解题思路也就是暴力算法，通过穷举所有可能的答案，然后再找到其中的最值。但是这样的算法一般都存在效率低下的问题，而适用动态规划算法的都会存在一个特点“重复子问题”。另外动态规划算法也一定具备“最优子结构”的特点。

何为最优子结构，也就是说通过最优的子问题，可以得到原问题的最值。举个栗子：

如果我们已知各个班级的最高成绩（子问题），需要求全校的最高成绩（原问题），这样我们只要比较各个班级的最高成绩就可以得出。

动态规划的另外一个核心是要找出正确的“状态转移方程”，这一步是所有动态规划算法中最难的一步，一般我们都会假设一个函数 f(i)为[0,i]为0-i的最优子问题结果，试图推导出f(i+1)的结果。

斐波那契数列问题严格来说不是一个动态规划问题，一方面它较为大众熟悉，另外一方面它比较适合我们来推导动态规划算法的基本原理和过程。

求斐波那契数列一般来说我们都会采用暴力递归的算法求解，具体求解过程可以通过一个递归树来表示。(注：如果你的算法需要优化，最后的优化思路是先画出算法的执行树，试图去寻找算法低效的地方加以改进)。

如果要计算原问题 f(10) ，我就得先计算出⼦问题 f(9) 和 f(8) ，然后要计算 f(9) ，我就要先算出⼦问题 f(8) 和 f(7) ，以此类推。

在这个过程中如果使用暴力递归的算法则存在大量的重复计算，如图中所示，f(8)会被计算两次，f(7)则要计算3次。这时我们很快就可以想到一个优化的思路，把每次计算过的值缓存起来，如果发现之前已经计算过了，直接拿来就好了。

这样我们就可以得到如下的解题过程：

从斐波那契数列开始讲解何为动态规划算法

有了这个解题过程，那么如果我们把这个过程反过来，从0开始计算岂不是不用递归了。我们设置一个数组对计算结果进行存储，可以得到如下的推演过程。

这里就可以得到动态转移方程，也就是斐波那契数列的定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。

具体解题代码如下：

public int fib(int N) { int[] nums=new int[N+1]; nums[0]=0;nums[1]=1; for (int i = 2; i <= N; i++) {    nums[i]=nums[i-1]+nums[i-2]; } return nums[N];}

细心的读者可以看到f(i)只和f(i-1)、f(i-2)相关，继续优化的话可以使用两个值缓存前两个的数据，这样可以进一步优化空间复杂度。当然斐波那契数列还有一种数学解法，这不是今天的重点。

我们通过对斐波那契数列的求解过程，推导出动态规划算法最难的状态转移方程。相信大家已经能够明白动态规划算法的基本原理和过程了。

接下来我们再看看今日的每日一题53.最大子序和的问题如何通过动态规划算法求解。

先看下题目：

这里如果使用暴力算法的会我们会找出所有连续子数组对其求和，我们可以先假设 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」。那么我们如何求 f(i) 呢？我们可以考虑a_i单独成为一段还是加入f(i−1) 对应的那一段，这取决于a_i和 f(i - 1) + ai的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：f(i)=max{f(i−1)+ai,ai}。

具体解题代码：

public int maxSubArray(int[] nums) { int n = nums.length, maxSum = nums[0]; for(int i = 1; i < n; ++i) { if (nums[i - 1] > 0) nums[i] += nums[i - 1]; maxSum = Math.max(nums[i], maxSum); } return maxSum;}