谈谈动态规划的本质

我心飞翔 分类:javascript

前言

在上一篇文章动态规划的文章中,我们先由 Fibonacci 例子引入到了动态规划中,然后借助兑换零钱的例子,分析了动态规划最主要的三个性质,即:

  1. 重叠子问题
  2. 最优子结构
  3. 状态转移方程

但是动态规划远不止这么简单。

今天这篇文章,让我们深入动态规划,一窥动态规划的本质。

我们既然要彻底搞清楚动态规划,那么一个不可避免的问题就是:

递归,贪心,记忆化搜索和动态规划之间到底有什么不同?

  • 动态规划递归 :只是单纯的空间换时间吗? 并不是,斐波那切数列的例子很好的推翻了这个观点。

  • 动态规划贪心:只是贪心的加强版吗?并不是,零钱兑换的例子同样推翻了这个观点。

那么,动态规划的核心到底是什么?

要回答这个问题,我们不妨先回答下面这个问题:

到底哪些问题适合用动态规划即?怎么鉴定 DP 可解问题?

相信当我们认识到哪些问题可以用 DP 解决,我们也就自然找到了 DP 和其它算法思想的区别,也就是动态规划的核心。

动态规划核心

首先我们要搞清楚,动态规划只适用于某一类问题,只是某一类问题的解决方法。

那么这“某一类问题”是什么问题呢?

聊这个之前我们有必要稍微了解下计算机的本质。

基于冯诺依曼体系结构的计算机本质上是一个状态机,为什么这么说呢?因为 CPU 要进行计算就必须和内存打交道。

因为数据存储在内存当中(寄存器和外盘性质也一样),没有数据 CPU 计算个空气啊?所以内存就是用来保存状态(数据)的,内存中当前存储的所有数据构成了当前的状态,CPU 只能利用当前的状态计算下一个状态

我们用计算机处理问题,无非就是在思考:如何用变量来储存状态,以及如何在状态之间转移:由一些变量计算出另一些变量,由当前状态计算出下一状态。

基于这些,我们也就得到了评判算法的优劣最主要的两个指标:

  • 空间复杂度:就是为了支持计算所必需存储的状态

  • 时间复杂度:就是初始状态到最终状态所需多少步

如果上述表述还不是很清楚,那我们还是举之前 Fibonacci 的例子来说:

  • 要计算当前 f(n),只需要知道 f(n - 1) 和 f(n - 2).

即:

  • 要计算当前状态 f(n),只需要计算状态 f(n - 1)和 f(n -2).

也就是说当前状态只与前两个状态有关,所以对于空间复杂度:我们只需保存前两个状态即可。

这也就很好的解释了为什么动态规划并不是单纯的空间换时间,因为它其实只跟状态有关。

由一个状态转移到另一状态所需的计算时间也是常数,故线性增加的状态,其总的时间复杂度也是线性的。

以上便是动态规划的核心,即:

状态的定义及状态之间的转移(状态方程的定义)。

那么如何定义所谓的“状态”和“状态之间的转移”呢?

我们引入维基百科的定义:

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

那就是通过拆分问题,定义问题状态状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

纸上谈来终觉浅,下边我们再来看一道同样非常经典的例题。

最长递增子序列

这是 LeetCode 第 300 题。

给定一个数列,长度为 N,求这个数列的最长上升(递增)子数列(LIS)的长度.

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为4

 

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4
解释:最长递增序列是 [0,1,2,3],因此长度为4
 

我们如何进行状态的定义状态间转移的定义呢?

一、状态的定义

首先我们应该进行问题的拆分,即进行这个问题子问题的定义。

所以,我们重新定义一下这个问题:

给定一个数列,长度为 N,

设 Fk为:给定数列中第 k 项结尾的最长递增子序列的长度

求 F1到 FN的最大值

是不是上边这个定义与原问题一样?

显然二者等价,不过明显第二种定义的方式,我们找到了子问题。

对于 Fk来讲,F1到 Fk-1都是 Fk的子问题。

上述新问题的 Fk 就叫做 状态

Fk为数列中第 k 项结尾的 LIS 的长度 即为状态的定义。

二、状态转移方程的定义

状态定义好之后,状态与状态之间的关系式,就叫状态转移方程。

此题以 Fk的定义来说:

设 Fk为:给定数列中第 k 项结尾的最长递增子序列的长

思考,状态之间应该怎么转移呢?

还记得我们之前说的拆分问题不,在这里同样我们可以沿用这一招,即拆分数据

如果数列只有一个数呢?那我们应该返回 1(我们找到了状态边界情况)。

那么我们可以写出以下状态转移方程:

F1 = 1

Fk = max ( Fi + 1 | i ∈(1,k-1))(k > 1)

即:以第 k 项结尾的 LIS 的长度是:max { 以第 i 项结尾的 LIS 长度 + 1 }, 第 i 项比第 k 项小

大家理解下,是不是这么回事~

回忆一下我们是怎么做的?

  1. 我们通过拆分问题进行了问题(子问题)的重定义(状态的定义);
  2. 通过状态的定义,再结合状态的边界情况,我们写出了状态与状态之间转移即状态转移方程的定义。

写出了状态转移方程,可以说到此,动态规划算法核心的思想我们已经表达出来了。

剩下的只不过是用记忆化地求解递推式的方法来解决就行了。

下面我们尝试写出代码。

代码

首先我们定义 dp 数组:

int[] dp = new int[nums.length];
 

(注意这里 dp 数组的大小跟上一篇文章兑换零钱的例子有一丢丢不同,即这里没有+1,大家可以再点击这里看下上一篇文章仔细理解一下。)

那么这里 dp 数组的含义就是:

dp[i] 保存的值即是给定数组 i 位之前最长递增子序列的长度。

那么我们的初始状态是什么呢?

我们知道状态的边界情况为:

F1 = 1

  • 即如果数据只有一位那么应该返回 1;
  • 当数据个数 > 1 时,如果整个数列没有出现第二个递增的数,那么同样返回 1.

所以,初始状态我们给 dp 数组每个位置都赋为 1.

Arrays.fill(dp, 1);
 

然后,我们从给定数组的第一个元素开始遍历,即写出外层的 for 循环:

for(int i = 0; i < nums.length;i++){
		......
}
 

当我们外层遍历到某元素时,我们怎么做呢?

我们得找一下,在这个外层元素之前,存不存在比它小的数,如果存在,那么我们就更新此外层元素的 dp[i]

如果某元素之前有比它小的数,那么这不就构成了递增子序列了吗?

因此我们可以写出内层 for 循环:

for (int j = 0; j < i; j++) {
    //如果前面有小于当前外层nums[i]的数,那么就令当前dp[i] = dp[j] + 1
     if (nums[j] < nums[i]) {
         //因为当前外层nums[i]前边可能有多个小于它的数,即存在多种组合,我们取最大的一组放到dp[i]里
          dp[i] = Math.max(dp[i], dp[j] + 1);
      }
}
 

两层循环结束时,dp[] 数组里存储的就是相应元素位置之前的最大递增子序列长度,我们只需遍历 dp[] 数组寻找出最大值,即可求得整个数组的最大递增子序列长度:

 int res = 0;
 for(int k = 0; k < dp.length; k++){
      res = Math.max(res, dp[k]);
 }
 

此题代码也就写完了,下面贴出完整代码:

class Solution {
  public int lengthOfLIS(int[] nums) {
      if(nums.length < 2) return 1;
      int[] dp = new int[nums.length];
      Arrays.fill(dp,1);
      for(int i = 0;i < nums.length;i++){
        for(int j = 0;j < i;j++){
          if(nums[j] < nums[i]){
            dp[i] = Math.max(dp[i],dp[j] + 1);
          }
        }
      }
      int res = 0;
      for(int k = 0;k < dp.length;k++){
        res = Math.max(res,dp[k]);
      }
      return res;
  }
}
 

这个题两层 for 循环跟之前兑换零钱的代码基本上差不多,大家可以结合上一篇文章再一起对比理解。

不同之处只是内层 for 循环的判断条件和状态转移方程的表达(如何更新 dp[]),这也是动态规划的本质所在。

小结

关于动态规划有很多误区和误解,比如最常见的可能就是说它是空间换时间,以及搞不清楚它和贪心的区别。

希望这两篇动态规划的文章能帮你消除这些误区,并且更好的理解到动态规划的本质,理解状态和状态方程。

当然,仅仅这两篇文章想说透动态规划是远远不够的,所以接下来会具体的讲解一些典型问题,比如背包问题、石子游戏、股票问题等等,希望能帮你在学习算法的道路上少走一些弯路。

如果大家有什么想了解的算法和题目类型,非常欢迎在评论区留言告诉我,我们下期见!

回复

我来回复
  • 暂无回复内容