LEETCODE常见算法之动态规划DP超详细白话讲解(上)

动态规划是Leetcode中比较常见的一类题型,面试时也经常被问到,还记得刚开始刷题时,我对这种题目非常恐惧,经常一头雾水,完全找不到思路。甚至看了别人的讲解后依然一知半解。但随着刷题量的增加,突然发现动态规划也没有那么复杂,绝大部分的题目都是大同小异,甚至让我感觉很多Hard级别的题目中,动态规划题目是相对容易的。本篇文章,我决定用实际的例子来分析,让大家明白动态规划到底是何方神圣。

先看下动态规划的定义:

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

摘自维基百科

定义里有一句话非常关键,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。如果你无法理解这句话的含义没有关系,下面我们会用实际的例子来说明。

另外,什么题适合使用动态规划来解题呢?这是一个非常有价值的问题,虽然我还没有刷满Leetcode的全部题目,不过我还是总结出了两点心得:

  1. 动态规划常常适用于有重叠子问题。
  2. 动态规划也适用于求最优子结构性质的问题。

遇到上述这两种问题,你会发现,问题本身可能会非常复杂,但是他的子问题或者孙问题会相对简单(甚至可以口算出来),并且子孙问题与原问题的逻辑是一致的,这时,动态规划思想就派上用场了。话不多说,我们先举个简单的例子压压惊!


题目一:

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。
你有多少种不同的方法可以爬到楼顶呢? 

题目链接:

也许大家对这道题目并不陌生,这是一个经典的斐波那契数列问题。本文抛开这个概念不提,我们重点讲下如何使用动态规划思想来分析。拿到DP题目时,我们需要考虑3件事:

  1. 将复杂问题拆分成子问题
  2. 找到子问题与原问题之间的关系
  3. 找到最小的子问题

我们一一来看,首先讨论如何拆分复杂问题。本题的题目就是一个复杂问题,因为你无法一下子得出结果。最终我们需要求出爬到第n阶台阶有多少种方法,那么谁是这个问题的子问题呢?我们马上想到的是爬到n-1阶台阶,n-2阶台阶,n-3阶台阶等等有多少种方法。这些问题我们称之为原问题的子问题。

接下来我们需要找到原问题与子问题之间的关联,这是解决动态规划问题的核心!也是大家常说的推导公式。对于本题,我们考虑,哪些台阶可以一步走到最后的第n阶台阶?因为一次只能迈出一阶或者两阶,因此只有从第n-1阶和第n-2阶台阶才能到达最终台阶。比如我们已知有x种方式能到达第n-1阶台阶,另外有y中方式能到达第n-2阶台阶,那么最终从这两个台阶到达第n阶台阶的方法数一定是x+y!我们用公式来表示:

// 设f(n)为到达第n阶台阶有多少种方法
f(n) = f(n-1) + f(n-2);

看到这里你可能会问,我怎么知道f(n-1)与f(n-2)的结果?是的,当前情况下我们确实不知道他们的结果,因为 f(n-1)与f(n-2) 仍然是复杂问题,只不过他比f(n)稍微简单了一丢丢而已。因此我们需要继续拆分子问题,按照上面的公式,将 f(n-1)和f(n-2)继续拆分:

f(n) = f(n-1) + f(n-2);

f(n-1) = f(n-2) + f(n-3);
f(n-2) = f(n-3) + f(n-4);
....

但是这样拆分下去,何时是个头呢?这就是我们要说的第三件事,找到最小的子问题!对于本题,最小子问题是f(1),也就是爬到第1阶台阶的方法数。这显然已经不是一个复杂问题了,我们用口算就可以知道f(1)等于1,即从第0阶台阶迈出一步到达第1阶台阶,除此之外你肯定找不到其它方式(因为本题只能向上走)!另外,f(0)也是我们需要考虑的,它代表了还没开始上台阶时的初始状态,来到这种状态的方式默认是1种(别和我说你可以坐飞机来也可以划船来!!)。

总结一下,到此为止我们分析出的结论:

1. f(0) = 1;
2. f(1) = 1;
3. f(n) = f(n-1) + f(n-2); 
4. 最终的答案是f(n)

当你看到这里,是不是已经有一点思路了?通过上面的结论,我们模拟一下计算过程,比如n等于8:

f(0) = 1;
f(1) = 1;
f(2) = f(0) + f(1) = 1 + 1 = 2;
f(3) = f(1) + f(2) = 1 + 2 = 3;
f(4) = f(2) + f(3) = 2 + 3 = 5;
f(5) = f(3) + f(4) = 3 + 5 = 8;
f(6) = f(4) + f(5) = 5 + 8 = 13;
f(7) = f(5) + f(6) = 8 + 13 = 21;
f(8) = f(6) + f(7) = 13 + 21 = 34;

实现代码:

使用动态规划方式时,按照上面的模拟发现,我们是从最小子问题开始逐步向复杂问题递进来解题的,这些子孙问题的解我们会在后面的计算中使用到,并且使用了不止一次,举个例子,比如f(3)的解,我们不仅在计算f(4)时会用到,计算f(5)时也会用到(有些复杂DP题目,同一个子问题解可能会被多次再利用),因此我们需要将这些子问题产生的中间过程的解保存起来,避免再次利用时产生重复计算。通常情况下,我们采用数组方式来存储这些子问题的解,这个数组我们称之为DP数组,也可以理解成记忆数组!它的存在,大幅降低了运算成本,对代码效率的提高有着举足轻重的作用。

int[] dp = new int[]; // dp数组或者叫做记忆数组

接下来上代码:

public int climbStairs(int n) {
    // DP数组,注意越界问题,数组长度定义为n+1
    int[] dp=new int[n+1];
    // 最小子问题的解
    dp[0]=1;
    dp[1]=1;
    // 从第二阶台阶开始循环
    for(int i=2;i<=n;i++){
        // 到达当前第i阶台阶的方法数
        dp[i]=dp[i-1]+dp[i-2];
    }
    // 返回到达第n阶台阶的方法数
    return dp[n];
}

对于这种简单的动态规划题目,网上绝大部分文章讲到这里就结束了。不过我们在这里讨论该题目,并不只是想要教你如何解题,更多的目的是在帮助大家理解DP算法的本质。因此,如果你还想更进一步的话,接下来的文章对你或许有所帮助。


动态规划的递归解释

无论你是否习惯使用递归方式来解DP题目,或是你是否熟悉递归思想,这都是你作为刷题者必须要了解的知识范畴,递归除了可以解决动态规划问题之外,经典的dfs深度优先搜索算法也是递归思想。我们知道,递归是拆分解决子问题的一种常见方式之一,在这里讨论递归问题,也是想帮助大家更好的理解DP,同时也为大家在做题时提供更多的思路。

言归正传,上文讲到的DP思想,我们是从最小子问题向复杂问题进阶的方式来解题,而递归思路则正好相反,我们需要从复杂问题开始着手思考,通常情况下,解题时我们需要定义一个递归函数(这不是废话吗?!),递归函数从最大问题开始,所有的子问题交给递归去解决,递归的终止条件是到达最小子问题为止。

我们还是利用爬楼梯的例子来做讲解。首先定义递归函数

int help(int n);

help(n)的返回值代表了爬到第n阶台阶的方法数。递归的核心思想与dp解法完全一样,我们想要知道help(n)的返回值,必须要知道 help(n-1) 以及 help(n-2)的结果,这正是递归函数的长项,因此,代码会变得非常简洁,大致如下:

int help(int n){
    int res = help(n-1)+help(n-2);
    return res;
}

另外,递归与循环有个相似之处,正是上文提到的终止条件,否则递归方法会无限执行下去。终止条件即是最小子问题,也就是该问题无法再继续拆分,很显然,本题的终止条件是当n等于1或者n等于0的时候,因此代码进化为:

int help(int n){
    if(n<=1) return 1;
    int res = help(n-1)+help(n-2);
    return res;
}

如果你不考虑执行效率的话,上面的代码完全可以解决动态规划问题。不过,你还记得上文讲到的DP数组吗?它的作用是为了防止重复计算。使用递归方式解题同样存在重复计算的问题,比如:

help(5) = help(4) + help(3);
help(4) = help(3) + help(2);

在计算4和5时,我们都递归调用了help(3)方法,这样会浪费掉大量的计算时间,因此,为了防止重复计算的产生,递归方法同样需要导入DP数组,这里我们将这个数组称为记忆数组更为精确。我们定义:

int[] memo = new int[]

其中memo[i]代表爬到第i阶台阶的方法数。我们将计算好的数值保存至记忆数组,当再次遇到该计算时,直接返回记忆数组中的数值即可。代码最终进化版本:

int[] memo; // 记忆数组
public int climbStairs(int n) {
    // 初始化记忆数组
    memo=new int[n+1];
    // 返回爬到第n阶台阶的方法数
    return help(n);
}
// 递归方法
int help(int n){
    // 递归终止条件:当n小于等于1时
    if(n<=1) return 1;
    // 如果记忆数组中存在返回爬到第n阶台阶的方法数
    // 直接返回该结果
    if(memo[n]>0) return memo[n];
    // 递归子问题求解
    int res = help(n-1)+help(n-2);
    // 将得到的解保存至记忆数组,避免之后重复计算
    memo[n]=res;
    // 返回该解
    return res;
}

以上就是递归方式来解决动态规划问题的思路。如果你经常看我的博客,你会发现我多次提到过,dp题目可以使用递归加记忆数组的方式来解题,其实我个人更加喜欢递归,leetcode上多数的dp题我都是用递归来搞定的,理论上,两种解题方式的核心思想并没有太大的差别,实现的时间复杂度也是完全一样,对于具体使用哪种方式更好,这是见仁见智的事情,总之,多一种思想多一条路,技多不压身,面试时如果你能向考官展现出两种解题方式,我想他们一定会对你刮目相看。


阶段小结

我们使用了一道简单的例子详细讲解了动态规划的核心思路,爬楼梯这道题目实际上就是存在多个重叠子问题,每个子问题的解题逻辑没有任何差别,我们通过已知的最小子问题的解题,来一步一步得出相对复杂的解,直到求解出题目给出的最终问题。

如果你已经初步掌握了动态规划的思想,你可以先消化一下。如果你还是没能搞懂上面的代码,也不要紧,不懂的地方你需要多看,最好使用编译器的debug功能来一行一行的调试,这对你理解代码会非常有帮助。实在不行,你也可以在文章下方留言,我会在第一时间给你做出解答。

接下来一篇文章,我会使用一道相对难一些的题目,对动态规划进行进一步的解释。

下文链接:LEETCODE常见算法之动态规划DP超详细白话讲解(下)

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode常见算法之动态规划dp超详细白话讲解/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

LEETCODE常见算法之动态规划DP超详细白话讲解(上)》有3条回应

  1. Pingback引用通告: LEETCODE常见算法之动态规划DP超详细白话讲解(下) - LEETCODE从零刷LEETCODE从零刷

  2. Pingback引用通告: LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下) - LEETCODE从零刷LEETCODE从零刷

  3. Pingback引用通告: LEETCODE刷题心得-你必须掌握的4类必考题型 - LEETCODE从零刷LEETCODE从零刷

发表评论

电子邮件地址不会被公开。