前言

本笔记是我挑战灵神的dp题单的算法笔记，可能是我最后一个关于题单的算法笔记了。做完这个题单的所有会做的基础题后，我将会转战hot100，挑战解析hot100的每一道题。

灵神说的好：

掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比学数学，只看书看视频而不做习题，是不能说学会的。

我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。所以推荐按照专题刷。

题目已按照难度分排序（右侧数字为难度分）。如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。

好的，话不多说，我们开始解析题目！至于为啥不解析dp算法本身？因为这玩意一种题目一个样，如果硬要概括啥是dp：

动态规划的核心思想是：将复杂问题分解成简单子问题，通过“记住”并复用子问题的答案，来避免重复计算，最终高效解决整个问题。

1 入门 DP

1.1 爬楼梯问题

1.1.1 简介

到底是入门题，难度从开局的及其简单到最后的中等难度，基本都可以接受。

老样子，咱们给题目分分类：

1.基础题(我能较快做出来)

(讲解)70. 爬楼梯 note:最最经典的dp题目，必须掌握

(讲解)746. 使用最小花费爬楼梯 约 1500 note:换汤不换药，只是将dp的主体从种类数量换成了花费，并需要引入最小值函数来保证每一步dp都是花费最小的

2.进阶题(我需要思考一下才能做出来)

3693. 爬楼梯 II 1560 note:是746的进阶版本

2466. 统计构造好字符串的方案数 1694 note:和下面的377做法一样

3.困难题(大体思路正确，但是需要纠正一些细节后才能做对)

(讲解)377. 组合总和 Ⅳ 约 1600 note:这类题目的本质就是爬楼梯，是2466的启蒙导师(对我来说)

(讲解)2266. 统计打字方案数 1857 note:非常新颖，第一眼可能看不出它是爬楼梯类型的

4.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)

无

故事的开头总是极其温柔的。作为dp章节的开头，这次的题目难度并不怎么高，但是下面的题目难度会变成咋样，就需要交给时间去验证了。

1.1.2 开始讲解！

我们先来看第一题：70. 爬楼梯，先看题。下面我讲的是DP的核心概念，必须掌握。

首先，我们需要讲问题的规模缩小。如果直接套多层循环暴力枚举每一步爬几步，既不好写(很难确定循环层数)，也很慢(时间复杂度会达到O(n的好几次方))。

这里，我们需要掌握一个基本概念：假设我一次可以爬1格或者2格楼梯，设第n层的爬楼梯方式种数为f(n)，那么，它一定满足如下式子：

$$ f(n)=f(n-1)+f(n-2) (n>=2) $$

因为，我可以从第n-2格跳2格上来，也可以从第n-1格跳一格上来，我只需要将这两格的可能性相加，就是我抵达第n格的爬楼梯方式的种数。

看到这个，你是不是会想到递归？当然可以，但是递归(纯递归，不带记忆化搜索)有很多缺点：

1. 指数级的时间复杂度与重复计算
   这是最致命、最核心的缺点。DP问题的本质是问题可以分解为重叠子问题。纯递归会盲目地、反复地计算这些完全相同的子问题。
2. 栈溢出风险。每一次递归调用都会在程序的调用栈上分配一个栈帧，用于保存局部变量、返回地址等信息。递归深度过深会耗尽栈空间，导致 StackOverflowError。
3. 低效的函数调用开销。函数调用本身涉及参数压栈、上下文保存、跳转等操作，这些操作比简单的循环和数组访问要慢。
4. 难以进行空间优化。自底向上的迭代DP，我们可以清晰地看到整个状态转移的过程，从而很容易进行空间优化（例如“滚动数组”技术）。

将纯递归排除掉后，我们剩下两种方式：

第一种就是将上面缺点的第一点给优化掉：引入记忆模块，使其摇身一变，成为记忆化搜索。

第二种就是抛弃递归，使用数组进行dp。

我们先来讲第一种。

1.记忆化搜索

何为记忆模块？上面的缺点说到：“纯递归会盲目地、反复地计算这些完全相同的子问题。”，那我不是将这些已经计算好的子问题的结果存储起来就好了？这样我下次要用的时候直接调用算好的，能省下指数级别的时间。

所以，选择哪种数据类型作为我们的记忆模块，就至关重要了。我们希望它存取快。毫无疑问，在大多数情况下，哈希表支撑的映射是最佳选择。因为它们存取的时间复杂度在大多数情况都是O(1)，非常快速。映射在常用竞赛语言中的对应如下：

好了，我们来使用记忆化搜索完成第一题：

class Solution {
    vector<int> memo;

    int dfs(int i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        int& res = memo[i]; // 注意这里是引用
        if (res) { // 如果之前计算过
            return res; //直接调用结果返回
        }
        return res = dfs(i - 1) + dfs(i - 2); // 否则计算当前楼梯种类，存入记忆中
    }

public:
    int climbStairs(int n) {
        memo.resize(n + 1); //给记忆数组分配内存
        return dfs(n);
    }
};

看完代码，肯定有同学迫不及待要问了：主播主播，你上面不是说要用哈希表吗，这里为啥用了数组？

因为楼梯的编号是具有规律性的，并且很密集，从1 2 3 ....n，当数据量很大的时候，哈希表的取值速度会退化回O(n)，这时候，数组依旧维持在O(1)的取值速度就能大杀四方了。当然，这是靠牺牲空间复杂度换来的。

由此，我们可以做如下总结：数据密集且有易理解的规律，选数组，省时间；数据稀疏且没啥规律，选哈希表(映射)，省空间。

2.数组dp

上面的记忆化搜索也只是解决了纯递归的第一个和第四个缺点，但是无法解决第二个(栈溢出风险)和第三个缺点(低效的函数调用开销)。为了彻底解决所有缺点，此时我们就要引入数组dp。这是dp的主力军，大部分dp题目的主流做法都离不开数组。

那么具体如何操作呢？一样的思路，我们聚焦下面这个式子：

$$ f(n)=f(n-1)+f(n-2) (n>=2) $$

有思路了吗？我们是不是只需要新建一个长度为n+1的数组dp，然后和递归做法一样，预先准备好dp[0]和dp[1]的数据，令它们都等于1。其中，dp[0]就是还没出发时的状态，这就对应一种"啥也不干"的爬楼梯方法，所以自然就初始化为1；而dp[1]是爬到第一格楼梯的方法数，显而易见只能从第0格，也就是还没出发时爬一格上来，所以也只有一种方法。后面从第二格开始，就可以使用下面这个式子直接往后递推了：

$$ dp[n]=dp[n-1]+dp[n-2] (n>=2) $$

使用数组取代递归，相当于：我们去掉了递归中的「递」，只保留「归」的部分，即自底向上计算。

看这道题的数组dp代码：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = f[1] = 1; //初始化0和1
        for (int i = 2; i <= n; i++) { //注意：从2开始
            f[i] = f[i - 1] + f[i - 2]; //往后递推
        }
        return f[n]; //返回结果
    }
};

这里还有一个要注意的地方：数组是从0开始到n结束的。其中n代表终点，0代表起点。所以在初始化dp数组时记得取n+1而不是n。

好了，经历了咱们上面的一题两"吃"后，你是不是有这样的疑惑：我到底是选记忆化搜索还是数组来进行Dynamic Programming？

先对比一下二者：

看完表格后，我相信大家心目中一定有了答案吧。反正在我看来，能用数组优先用数组，用不了再换记忆化搜索。

接着我们来看第二题：746. 使用最小花费爬楼梯，先看题。

这一题就和上面有些不一样了，我们不能无脑往后递推了。因为：cost数组每一格的值是不确定的，我们没法确定我是爬1格省钱还是爬2格省钱。你看示例2的例子：

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

1夹杂在100之间，我就问你阴不阴？但凡踩错一步，费用直接涨100倍。

这时候我们就需要引入贪心的思想了。为了使总花费最少，我们只需要将每一步的花费降低到最少即可。

具体怎么做呢？我们依旧起dp数组，只不过这时候我们dp的主体就是花费了，而不是第一题的方法数量。

老样子，先将dp[0]初始化为0，因为站在原地不要钱；再将dp[1]也初始化为0，因为它是另一个起点(题目允许自由选择起点为第0个或第1个楼梯)。后面，我们开始递推：我管你是从上一个还是上上个楼梯爬上来的，哪边(历史总花费+跳上来到我这一格的花费)最小我就选哪边。

$$ dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])(i>=2) $$

这样一步步往后递推，保证每一步选的都是花费最小的方法，最后留下来的dp[n]就自然是全局最小花费了。看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1); //初始化dp数组
        dp[0]=0;dp[1]=0;
        for (int i=2;i<=n;i++) {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};

经过前两题的修炼，我们来看第三题：377. 组合总和 Ⅳ，先看题，这题的难度会稍微高一点。

看完题目，你肯定一脸懵：这还是爬楼梯问题吗？

其实是的，只是我们需要转化一下题意。

就拿例1来讲吧：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

target=4，说明我们需要从[1,2,3]中取数，使其总和为4。这不就是：我可以一次爬1步，2步或者3步，总共有4个楼梯，求我爬楼梯的方法总数吗？

大多数人的第一反应是，可以继续用第一题一样的斐波那契数列型的递推公式来完成这道题目，代码可能像这样：

class Solution {
public:
    int climbStairs(int n) { //此处n
        vector<int> f(n + 1);
        f[0] = f[1] = 1; //初始化0和1
        f[2]=2;
        for (int i = 3; i <= n; i++) { //注意：从3开始
            f[i] = f[i - 1] + f[i - 2] + f[i - 3]; //往后递推
        }
        return f[n]; //返回结果
    }
};

是的，上面的代码没错，确实适用于用例1，但是nums数组的大小和种类一直在变化，固定的-1 -2 -3肯定行不通，我总不可能给每一个用例都量身定制一套代码吧？

所以，我们接下来的任务就是想出一个逻辑来帮我们自动处理这套递推逻辑。推广一下经典的爬楼梯逻辑，就是：

要爬到第 i 阶楼梯，可以选择最后一步爬 x 阶，只要 i≥x。所以，到达 i 的所有方案数 = 所有能到 i−x 阶的方案数之和

就拿上面的用例举例子，我爬到第4个台阶的方法总和是从第3 2 1格台阶爬上来的方法数总和，因为nums=[1,2,3]，所以能到达第四个台阶的台阶就是第1 2 3个，所以我们要累加那几个台阶的方法。

有了这个逻辑，我们直接在内层再开一个循环帮我们自动寻找可用的台阶，并且累加起来就行。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<ll> dp(target+1,0);
        dp[0]=1; //经典的啥也不做也算一种
        for (ll i=1;i<=target;i++) {
            for (ll num:nums) { //枚举可用的爬楼梯步数
                if (num<=i && dp[i-num]<=INT_MAX-dp[i]) { 
                    //这里的第二个条件是为了防止溢出报错，直接把数组类型改成unsignedint也行，就不需要写这个条件了
                    //题目保证答案不会超出整数范围，所以我们为了避免报错，才加这个条件
                    dp[i]+=dp[i-num]; //累加上前驱楼层的方案数
                }
            }
        }
        return dp[target];
    }
};

再加深一下理解，我新增的内层循环其实是在干这个事情：

我现在在第 i 阶，想知道有多少种走法能到这里。
我枚举我最后一步跨了多少格（这就是内层循环）。
每种跨法对应“从哪一级上来的”，
所以我就累加这些“前驱楼层”的方案数。

最后，我们终于来到了第四题：2266. 统计打字方案数，先看题。这题的难度又上升了一些。

其实就是这题的马甲更厚了，让人一时半会很难想明白怎么用dp。咱们一步一步来拆解。

首先，我们能发现，一串叠在一起的数字，它代表了多种可能。直接看用例1：

输入：pressedKeys = "22233"
输出：8
解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。

接着，容易发现：222可能是aaa，也就是每次都只爬一格，爬3次爬上了3格高的楼梯；222也可能是ab，也就是1+2的爬楼梯组合；也可能是2+1的组合...这不就是爬楼梯吗？

然后22233，不就是两个个爬楼梯问题的叠加吗？

那我们的思路就很明确了：

1. 算出每个数字按的个数。
2. 分别用爬楼梯模型解决单个数字(注意：数字7和9需要单独处理，爬的步数有4种可能)
3. 再使用乘法原理，将所有数字的种类数累乘，就是最终的方案数

直接看代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;

class Solution {
public:
    int dp_3(int n) { //处理除了7和9的按键结果种类数量 是爬楼梯问题
        vector<ll> dp(max(3,n+1));
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for (int i=3;i<=n;i++) {
            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%MOD;
        }
        return dp[n];
    }
    int dp_4(int n) { //单独处理7和9
        vector<ll> dp(max(4,n+1));
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for (int i=4;i<=n;i++) {
            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4])%MOD;
        }
        return dp[n];
    }
    int countTexts(string pressedKeys) {
        int n = pressedKeys.size();
        ll ans=1;
        int cnt=0;
        for (int i=0;i<n;i++) { //主循环遍历字符串
            cnt++; //维护一个计数器，计算每个数字出现次数
            if (i==n-1 || pressedKeys[i]!=pressedKeys[i+1]) { //到达最后一位或者到达不同数字串的分界点时结算
                if (pressedKeys[i]=='7' || pressedKeys[i]=='9') {
                    ans=ans*dp_4(cnt)%MOD; //累乘时记得取余，否则溢出
                }else {
                    ans=ans*dp_3(cnt)%MOD; //累乘时记得取余，否则溢出
                }
                cnt=0; //结算后重置计数器
            }
        }
        return ans%MOD;
    }
};

好了，到这里，我们爬楼梯题型的算法笔记就讲解完毕了。下次见面，就是对我来说比这玩意还熟悉的打家劫舍模型了(尤其记得9月的csp认证的第四题我靠这玩意捞了20分)。