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

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

先看下动态规划的定义：

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

摘自维基百科

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

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

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

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

---

题目一：

爬楼梯

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

题目链接：

• 英文版： https://leetcode.com/problems/climbing-stairs/
• 中文版： https://leetcode-cn.com/problems/climbing-stairs/
• 查看题目信息： https://leetcode.jp/problemdetail.php?id=70

也许大家对这道题目并不陌生，这是一个经典的斐波那契数列问题。本文抛开这个概念不提，我们重点讲下如何使用动态规划思想来分析。拿到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超详细白话讲解/