前言

本笔记是我挑战灵神的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分)。

1.2 打家劫舍

1.2.1 简介

先看看本次做题情况：

题目难度相比于上面的爬楼梯问题有所上升。

老样子，下面给题目难度分分类：

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

(讲解)198. 打家劫舍 Note:这道题是打家劫舍求最大金额的代表，必须掌握，下面还有另一种类型

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

(讲解)213. 打家劫舍 II Note:是上面198题的变式，需要想到分类讨论后取最佳

(讲解)2320. 统计放置房子的方式数 1608 Note:这道题是打家劫舍求方案数量的代表

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

(讲解)740. 删除并获得点数 Note:是上面198基本算法模型的改进，需要先将值转换为范围分布密度数组，再进行打家劫舍

4.地狱题(需要反复理解题解才能勉强自主复现代码)

(讲解)3186. 施咒的最大总伤害 1841 Note:这道题目应该是不属于上面的任何一个模型，仅仅只能说它属于打家劫舍的范畴，比较难

这次的题目给我一种很精炼的感觉——仅仅5道题目，就发展出了这么多不同的流派！所以今天我需要全部讲解。

1.2.2 开始讲解

首先来看第一题：198. 打家劫舍，先看题目。

题目说，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

所以，我们如果准备偷这一间房屋，就不能偷前一个房屋；如果不偷这一个房屋，那么前面的房屋偷不偷都行。

那我如何决定偷不偷呢？肯定怎么钱多怎么来！

这样，我们就大致判断出：我们构建的dp数组，每个房间都有2个状态，偷与不偷。然后，我们在处理每一个房屋的时候，分别处理偷与不偷的状态。这里我们设定下标0为不偷此房屋的金额累计，下标1为偷此房屋的金额累计：

1. 如果不偷这个房屋i，那么dp[i][0]=max(dp[i-1][0],dp[i-1][1]);，直接继承前面的最佳情况，保证每一步都是最佳的(有点贪心思想在里面)；
2. 如果要偷这个房屋i，那么dp[i][1]=dp[i-1][0]+nums[i];，也就是我们别无选择，只能继承上一个房屋不偷的状态，然后再加上偷这个房屋的收益往后传。

逻辑已经很清楚了，简单看一眼代码：

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

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>{0,0});
        dp[0][0]=0;dp[0][1]=nums[0]; //初始化第一间屋子
        for (int i=1;i<n;i++) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]); //如果不偷这家，那就选最大的继承
            dp[i][1]=dp[i-1][0]+nums[i]; //偷的话，上一家就不能偷
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

接着我们来看第二题：213. 打家劫舍 II，先看题。

这题和第一题其他地方基本一致，就是多加了一个首尾房屋不能两个全偷的限制。

解析一下这个限制：这说明我们可以偷第一间，不偷最后一间；或者偷最后一间，不偷第一间；也可以两个都不偷。

这样，我们是不是可以直接分类讨论了？

起两个dp数组，所有参数可以一模一样，只需要改一下取答案的位置，逻辑按照第一题一模一样照搬就行：

1. 如果选择偷第一间，那就把dp循环的范围往前缩小一位(这里就需要注意数组过小越界的问题了)，然后取答案直接在倒数第二位取；
2. 如果选择偷最后一间，那就在初始化dp时选择第二间屋子，然后从第二间屋子dp到最后一间屋子即可，然后取答案直接在最后一位取。

然后就是注意一下范围问题。我这里是直接选择小数组特判，防止后面越界。

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

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n==1) return nums[0];
        if (n==2) return max(nums[0],nums[1]);
        vector<vector<int>> dp1(n,vector<int>{0,0}),dp2(n,vector<int>{0,0});
        //1.确定偷第一家，确定不偷最后一家
        dp1[0][1]=nums[0];
        for (int i=1;i<n-1;i++) { //dp的终点往前缩小一位
            dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
            dp1[i][1]=dp1[i-1][0]+nums[i];
        }
        //2.不偷第一家，确定偷最后一家
        dp2[1][0]=0;dp2[1][1]=nums[1];
        for (int i=2;i<n;i++) { //dp的起点往后推一位
            dp2[i][0]=max(dp2[i-1][0],dp2[i-1][1]);
            dp2[i][1]=dp2[i-1][0]+nums[i];
        }
        return max(max(dp1[n-2][0],dp1[n-2][1]),max(dp2[n-1][0],dp2[n-1][1]));
    }
};

顺带说一下，两个房屋都不偷的情况也已经落实在这两个分类讨论的情况里面了，不需要再另外写。

好了，我们来看第三题：2320. 统计放置房子的方式数，先看题。

在这道题，我们需要和前面的两道题目切割一下了：这是打家劫舍题型的另一种类型。

首先我们能发现，街道两侧的房屋分布其实是障眼法，我们只需要处理一侧的房屋分布之后使用乘法原理平方一下就是两侧的方案种类数量了。所以，我翻译一下这道题目：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，偷盗房屋的方式有多少种。将答案平方后返回。

其实就是将上面的金额最佳换成了种类数量计算。我们继续沿用上面的二维dp数组，只需要稍微更改一下：

1. 如果第i格不建房子，那么第i-1格建不建都行，得把建与不建的方案总数都加上：dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;

2. 如果第i格要建房子，那么第i-1格就不能建了，只能继承第i-1格的方案数了：dp[i][1] = dp[i - 1][0];。

   这里其实有点类似于上面的377. 组合总和 Ⅳ：第一反应看这个式子好像有问题，直觉不应该加一吗？

   但是其实，你想象一下：把前面这么多种方案从上到下排起来，到了这个房子，不就相当于在每种方案后面把自己拼上去吗，方案总数并没有增加。所以，这就是直接继承前面的数量而不加一的真正原因。

这样，这道题目的逻辑就很清楚了，直接看代码：

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

class Solution {
public:
    int countHousePlacements(int n) {
        const long long MOD = 1000000007;
        // dp[i][0]：一侧前 i 个地块，第 i 个不建房的方案数
        // dp[i][1]：一侧前 i 个地块，第 i 个建房的方案数
        vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));

        dp[1][0] = 1; // 不建
        dp[1][1] = 1; // 建

        for (int i = 2; i <= n; ++i) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
            dp[i][1] = dp[i - 1][0];
        }

        long long oneSide = (dp[n][0] + dp[n][1]) % MOD;
        return (int)(oneSide * oneSide % MOD);
    }
};

当然，这道题的式子还可以简化，我们递推一下：

我们记 f[i] = ways_one_side(i) = dp[i][0] + dp[i][1]，推一下关系：

f[i] = dp[i][0] + dp[i][1]
     = (dp[i-1][0] + dp[i-1][1]) + dp[i-1][0]
     = f[i-1] + dp[i-1][0]

而

dp[i-1][0] = dp[i-2][0] + dp[i-2][1] = f[i-2]

所以得到：

f[i] = f[i-1] + f[i-2]

这就是标准的斐波那契递推。

如果知道了可以这么做，那么题目的代码可以再次化简：

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

class Solution {
public:
    int countHousePlacements(int n) {
        vector<ll> dp(n+1);
        dp[0]=1;dp[1]=2;
        for (int i=2;i<=n;i++) {
            dp[i]=(dp[i-1]+dp[i-2])%MOD;
        }
        return dp[n]*dp[n]%MOD;
    }
};

接着我们来看第四题：740. 删除并获得点数，这题就比较有难度了，先看题。

初看，这题貌似就是经典的打家劫舍问题，但是我们没法直接上手，见下方用例：

示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

假设我遍历到第二个三，我的前一位和后一位都是3，就无法根据索引来开展dp了。当然，只需要转化一下就可以。

那么如何转化呢？这时候就要引入我们今天的新知识：值域数组。

那么这个数组有啥用呢？你可以理解为：

把离散、重复的数轴上的点，转换成连续区间的 DP 数组结构。

看看下面的例子，你就能理解了。

比如 nums = [2,2,3,3,3,4]

那么 sum 数组为：

这样，我们只需要在这个值域数组上面dp，就可以正常的通过索引的加减来处理相邻元素的问题。

其他逻辑和第一题一模一样，就不再赘述。看代码：

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

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //1.预处理
        sort(nums.begin(), nums.end());
        int m=nums[nums.size()-1];
        vector<ll> sum(m+1,0);
        for (auto x:nums) {
            sum[x]+=x;
        }
        //2.开始dp
        vector<vector<int>> dp(m+1,vector<int>{0,0});
        dp[1][0]=0;dp[1][1]=sum[1];
        for (int i=2;i<=m;i++) {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+sum[i];
        }
        return max(dp[m][0],dp[m][1]);
    }
};

其中值得说道一下的一点是：这个频次数组直接将所有数都加起来了，这样在dp时相当于一次"消掉"好几个数，写起来简单也能省时间。

最后我们来看第五题：3186. 施咒的最大总伤害，先看题。

首先，看到题目，我们可以发现和上面第四题有点类似：可以继续使用值域数组来压缩空间。

然后，难点来了：这题在取了i之后，不仅仅取不了i-1，连i-2都取不了了！

如果我们把不同伤害值排序后得到 a[0].first < a[1].first < ... < a[n-1].first：

• 当前处理 a[i] = x 时，它可能同时和好几个前面的伤害值冲突：

  • 和 a[i-1] 冲突（差值 ≤ 2）
  • 甚至可能还和 a[i-2] 冲突（比如 1,2,3 这种）
  • 一直到某个最早的位置 j，使得 a[j].first >= x-2，更前的才安全

所以如果你想“选 i”，你不能简单地说“那就看 dp[i-1][0]”，
因为 i 可能还会和 i-2, i-3,... 冲突，冲突区不是只一格，而是一个段 [j..i-1]。

所以：只依赖 i-1 的那种简洁 dp[i][2] 转移，在这里是不成立的。

那么我们该怎么做呢？用全新的方式，概括起来就是：将拿与不拿的状态合并在一起，然后通过指针来寻找不拿情况下的前驱最大值。

具体怎么操作：

把“选/不选”的两种情况折叠进 max(...) 里面：

• 不选 a[i]：
  f[i+1] = f[i]
• 选 a[i]：
  只能搭配那些伤害 ≤ x-3 的种类
  这些种类刚好是 a[0..j-1]，它们的最优解就是 f[j]
  所以“选 i”情况的总收益是 f[j] + x * c

好了，我们直接看代码：

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

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        //1.预处理
        sort(power.begin(), power.end());
        unordered_map<int,int> cnt;
        for (auto x:power) cnt[x]++;
        //2.开始dp
        vector<pair<int,int>> a(cnt.begin(), cnt.end()); //此数组存储伤害及其数量
        sort(a.begin(), a.end()); //从高到低排序
        int n=a.size();
        vector<ll> f(n+1);
        for (int i=0,j=0;i<n;i++) {
            auto &[x,c] = a[i];
            while (a[j].first<x-2) {
                j++;
            }
            f[i+1]=max(f[i],f[j]+(ll)x*c);
        }
        return f[n];
    }
};

以防你看不懂，下面我再把核心dp部分的代码拆开讲讲：

vector<ll> f(n+1);
for (int i=0,j=0;i<n;i++) {
    auto &[x,c] = a[i];
    while (a[j].first < x-2) {
        j++;
    }
    f[i+1] = max(f[i], f[j] + (ll)x*c);
}
return f[n];

我们逐行拆：

1）状态定义

• f[k] 表示：
  在考虑 a[0..k-1] 这前 k 个不同伤害值时，能得到的最大总伤害。

所以最后答案是 f[n]，表示考虑完所有不同的伤害值。

2）循环变量

for (int i=0,j=0;i<n;i++) {
    auto &[x,c] = a[i]; // 当前考虑的伤害值为 x，数量为 c
    ...
}

• i：当前考虑的伤害值下标
• x = a[i].first：当前的伤害值
• c = a[i].second：这种伤害值的咒语数量
• 当前如果全选这种伤害的咒语，可以获得的伤害是 x * c

3）约束条件是什么？

题目说：使用伤害值为 x 的咒语时，不能使用伤害为 x-2、x-1、x+1、x+2 的咒语。

也就是说：

• 如果我打算选伤害值为 x 这一类咒语，
• 那就不能选伤害落在 [x-2, x+2] 的任何别的咒语。
• 但可以选比 x-3 更小的，或者 x+3 以上更大的。

在当前 i 正在处理 x 的时候，我们只考虑「左边」的，也就是更小的那些伤害值（因为 DP 是从小到大）。

所以：

如果选择 x，那在它左边最多只能选那些伤害值 ≤ x-3 的种类。

4）j 指针在干什么？

while (a[j].first < x-2) {
    j++;
}
f[i+1] = max(f[i], f[j] + (ll)x*c);

• 数组 a 是按伤害从小到大排的。
• 我们希望 j 满足：
  a[0..j-1].first <= x-3，a[j].first >= x-2

while (a[j].first < x-2) j++;
循环结束时，j 是第一个满足 伤害值 >= x-2 的下标。

于是：

• a[0..j-1] 中的伤害值都 ≤ x-3，都可以和 x 共存
• f[j] 正好表示：
  在 a[0..j-1] 这些完全合法的前面的伤害值中，能取得的最大总伤害

所以，当我们想「选当前这个伤害值 x」时：

能搭配的最佳历史答案就是 f[j]，
再加上当前选择价值 x*c。

因此：

选当前 x 的收益 = f[j] + x * c;
不选当前 x 的收益 = f[i]; // 因为 f[i] 就是考虑到 a[0..i-1] 的最优
f[i+1] = max(不选, 选)
       = max(f[i], f[j] + (ll)x*c);

这就是标准的 DP 转移式。

5）为什么用双指针而不是二分？

你可能注意到了：
对于每个 i，我们都要找到一个最小的 j 使得 a[j].first >= x-2。
这个完全可以用二分查找做：j = lower_bound(...)，复杂度 O(n log n)。

但这里用了双指针技巧：

• i 从 0 递增到 n-1
• j 也是单调递增的
• a[j].first 也是单调不减
• 一次遍历中 j 只会从 0 增到 n，整体 O(n)

因此总复杂度：

• 排序：O(n log n)
• DP + 双指针：O(n)
• 总体：O(n log n)

这次的5道题目难度循序渐进，还是比较有挑战的。那么，下次，最大子数组和问题见！

1.3 最大子数组和 11月25日更新

1.3.1 简介

先看看我本次的做题情况：

这次的题目的难度还是比较温和的，即使是最后一道hard题目，题解过一下就会写了。

老样子，列举一下本次难度：

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

(例题-精讲)53. 最大子数组和 Note:这道题目是这一类题目的入门题，也是下面几道题目的基础。这次的题目变式比较小，这六道题目用一样的方法都能解决

2606. 找到最大开销的子字符串 1422 Note: 不过是相当于上一题绕了一下，多处理了一步，换汤不换药

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

(讲解)1749. 任意子数组和的绝对值的最大值 1542 Note:这题有个误区：如果直接用绝对值去dp，会导致前面的数干扰相邻两个数之间的判断，需要分别求 最小最大子数组之和 再取绝对值最大的那个

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

(讲解)918. 环形子数组的最大和 1777 Note:这题让我想起了滑动窗口的1423. 可获得的最大点数，和这道题正难则反的思路一模一样，很有意思

(讲解)2321. 拼接数组的最大分数 1791 Note:这是这波难度分数最高的hard题目，但是题解比较好理解，灵神讲的很好。开局的公式只要推出来了，后面就是白给

4.地狱题(需要反复理解题解才能勉强自主复现代码)

(讲解)1191. K 次串联后最大子数组之和 1748 Note:这题虽然分数不如最后一题高，但是是我觉得最难的。你需要想到去分类讨论，然后把问题转化成最终求解1个或者2个数组的最大子数组和的问题

好的，题目难度列举到这里，下面我们开始讲解！

1.3.2 开始讲解

首先，我们看第一题：53. 最大子数组和，这题是这一系列题目的基础，所以我会讲的比较细。

首先阅读题目，它要求我们找出一个子数组，使得它的和最大。

这时候，我们就需要引入一个算法概念了。算法本身简单粗暴，很好记住，但是我和它第一次见面的时候还是费了不少时间去理解的。所以我先讲这个算法的实操，再讲这样做为什么行。

这个算法叫Kadane 算法，专门用来计算最大(最小)子数组和。它的基本操作是这样的：

1. 定义一个dp数组，长度为要计算最小子数组和的数组a的长度n。
2. 将dp[0]初始化为a[0]。
3. 开始遍历数组a。dp[i]的值取dp[i-1]+a[i]与a[i]的最大值。意思就是：如果继续将当前数字接在前面会更大，那就接上；反之，就放弃前面的子数组，从这个数字重新开始。
4. 最后，由于我们不知道哪个子数组的和是最大的，也就是我们肯定不知道这个和最大的子数组在哪里结尾，所以我们需要再遍历一遍这个dp数组，取最大值即为最终答案。

算法本身是很简单的，你肯定看了一眼就记住了。但是为什么这样看起来这么"渣"的做法能求出最大值呢？原理就是，你熟悉的那两个字，贪心。

在上面的步骤三，为啥如果当前数字接在前面会更大，我才接上，否则我就放弃？

那是因为我并不知道后面的情况如何，我只把握着这一个数字和截至前一个数字的最大子数组和，如果加上这一位数字还不如断开从当前数字重新开始更大，那就说明前面的最大子数组里面负数偏多，使得总和为负数，这样子如果还强行接上，会拖累当前数字，无论当前数字是正数还是负数。

所以，为了防止当前数字被拖累，我们这里相当于做了一个选择题，预先计算好 当前数字接上前面数字 和 从当前数字重新开始 的两种结果，取最大，让每一步的操作都取最大结果，这样才能保证每一个正数的努力不会被埋没。

如果你理解了上面的原理和操作方法，这道题目可以直接秒了，代码如下：

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0]=nums[0];
        //dp
        for (int i=1;i<n;i++) {
            dp[i]=max(dp[i-1],0)+nums[i];
        }
        //找最大
        int ans = dp[0];
        for (auto x:dp) ans = max(ans,x);
        return ans;
    }
};

接着，我们来看第二题：1749. 任意子数组和的绝对值的最大值，先看题。

看完题，相信很多人可能会想写类似于下面的逻辑：

dp[i] = 以 i 结尾的、绝对值最大的子数组和
dp[i] = 在下面两个中选 |.| 更大的那个：
    1）dp[i-1] + nums[i]   （在前面的基础上扩展）
    2）nums[i]             （从自己重新开一段）
答案 = max_i |dp[i]|

但是这样是错的。因为将前面的和绝对值之后存进dp，下一个数就不知道上一个数的和是正是负了，造成了信息的丢失。

即使你单纯用绝对值比较，还是在dp里面存放和的正负，这样的逻辑看似正确，实则答案还是错的。为什么呢？

因为：

“在位置 i−1 处，绝对值最大的那个子数组和”
不一定是“能在后面扩展出全局最优解的那个子数组和”。

引入绝对值，造成了非线性的麻烦，破坏了最优子结构。

那么我们该怎么做呢？我们需要彻底抛弃绝对值。

先想想我们如何让一个数的绝对值大：要么是这个数是正数，很大；要么是这个数是负数，很小。

那我们岂不是分别求这个数组的最大子数组和和最小子数组和，然后取绝对值最大者为答案，不就完事了？

这相当于去试探两个极端：要么疯狂取正数，要么疯狂取负数，尽量别让正负直接相互抵消，这样绝对值才能最大。

明白了吗？讲完了思路，代码随便写了。

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

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp1(n),dp2(n);
        dp1[0]=nums[0];dp2[0]=nums[0];
        for (int i=1;i<n;i++) {
            dp1[i]=max(dp1[i-1],0)+nums[i];
            dp2[i]=min(dp2[i-1],0)+nums[i];
        }
        int ans = abs(dp1[0]);
        for (int i=0;i<n;i++) {
            ans = max(abs(dp1[i]),ans);
            ans = max(abs(dp2[i]),ans);
        }
        return ans;
    }
};

接着来看第三题：918. 环形子数组的最大和，先看题，这题还是很有意思的，经典正难则反，将我的思绪带回了暑假刷滑动窗口的那个下午。

如果你想从正面正常做这道题，还是比较难的。数组是环形的，我暂时想不出怎么处理环形数组dp；或者用古老的办法：遍历起点，将每一个起点都试一试，生成和数组长度一样多的数组，虽然能做，但是时间复杂度翻倍。

那么怎么做呢？我们思考一下：最大子数组和无非也就分两种情况，一种是子数组的起点在子数组的终点左边，相当于起点<=子数组起点<=子数组终点<=终点，此时还没利用到环形数组的特性；另一种情况就是起点<=子数组终点<=子数组起点<=终点，相当于利用了环形数组的特性，从靠右的子数组起点一直取到终点后又回到起点继续取，直到子数组的终点。

第一种情况的最大子数组之和就很方便了，正常算就行；那么第二种情况呢？上面说了，正难则反，我们直接算这个数组的最小子数组之和，然后再用这个数组的和减去我们算出来的最小子数组之和，不就行了？

然后我们也不清楚这两种情况哪种是最大的，最后再取最大即可。

思路讲完了，代码直接秒：

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

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        //1.先计算数组总和
        ll n = nums.size();
        ll sum=0;
        for (auto x:nums) {
            sum+=x;
        }
        //2.开始正常找最大子数组
        vector<ll> dp1(n),dp2(n);
        dp1[0]=nums[0];
        dp2[0]=nums[0];
        for (int i=1;i<n;i++) {
            dp1[i]=max(dp1[i-1],0LL)+nums[i];
            dp2[i]=min(dp2[i-1],0LL)+nums[i];
        }
        //3.找最大和最小
        ll maxS=dp1[0];
        for (auto x:dp1) maxS = max(maxS,x);
        ll minS=dp2[0];
        for (auto x:dp2) minS = min(minS,x);
        //4.分类讨论
        if (maxS<0) return maxS;
        return max(maxS,sum-minS);
    }
};

接着我们来讲第四题：2321. 拼接数组的最大分数，先看题。

设 $s_1 = \sum_{i} nums_1[i] $。

交换$[left, right]$ 范围内的元素后，对于 $nums_1'$ 有 $ \sum_{i} nums_1'[i] = s_1 - \left(nums_1[left] + \cdots + nums_1[right]\right) + \left(nums_2[left] + \cdots + nums_2[right]\right)$

合并相同下标，等号右侧变形为 $ s_1 + \left(nums_2[left] - nums_1[left]\right) + \cdots + \left(nums_2[right] - nums_1[right]\right) $

设 $diff[i] = nums_2[i] - nums_1[i]$，上式变为 $s_1 + diff[left] + \cdots + diff[right]$

所以这样一转化，这道题目就变成了求diff数组的最大子数组和。

但是，上面只讨论了一种情况，是将nums2迁移到nums1并以nums1为主，所以我们可以写好这套逻辑后，简单交换一下就能获得另一种情况的结果。然后两种情况取最大就行了。

思路很清楚了，代码直接秒：

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

class Solution {
public:
    int maxSubArray(vector<int>& a,vector<int>& b) {
        //1.先求d[i]
        int n = a.size();
        vector<int> d(n);
        for (int i=0;i<n;i++) {
            d[i]=b[i]-a[i];
        }
        //2.对着d[i]做最大子数组
        vector<int> dp(n);
        dp[0]=d[0];
        for (int i=1;i<n;i++) {
            dp[i]=max(dp[i-1],0)+d[i];
        }
        //3.取最大
        int ans = dp[0];
        for (auto x:dp) ans = max(ans,x);
        //4.求一下a数组的和
        int sumA = 0;
        for (auto x:a) sumA+=x;
        //5.返回结果
        return sumA+ans;
    }

    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        return max(maxSubArray(nums1,nums2),maxSubArray(nums2,nums1)); //两种情况都算算，取最大
    }
};

最后，我们来到了第五题：1191. K 次串联后最大子数组之和，先看题。这是这次讲解最难的题。

首先我们要搞清楚一点：数组串联k次，如果只是简单将其串联起来然后再求最大子数组和，数据规模会达到10^10，会严重超时。

所以，我们需要找到一个规律，来避免重复计算中间这些一模一样的数组。

我们将k一点点提升。当k=1时，就是简单的最大子数组和问题，直接求就行。

当k=2时，就是将两个数组简单拼起来，可以在拼起来后直接求最大子数组和问题。

当k>=3时呢？我们可以将这个数组分为三部分：第一个数组，中间的若干个数组和最后一个数组。

我们可以意识到：如果单个数组的和是正数，那肯定是拿的越多最终答案越大；反之，如果是负数，那最好一个都不要拿，因为负数只会让结果更小。当然，如果是0那可拿可不拿。

我们令单个数组为A。当k>=3时，后面的情况都是一样的，所以我讲解一下k=5的情况，你就懂了。

1. 当sum(A)>=0时，我们肯定把全部的中间的若干个数组全都取过来：A(AAA)A，我们再移项一下：AA(AAA)。

   接着，然后由于里面的数字有正有负，所以在A内部取最大子数组和是一定比sum(A)更大的。

   我们对着前两个A求最大子数组和，然后再加上中间的3个A的总和，就得到了这种情况的答案：maxSubArrSum(AA)+(k-2)*sum(A)

2. 当sum(A)<0时，我们肯定是一个中间数组都不想取。依旧移项，从A(AAA)A到AA(AAA)，相当于我们就只需要对前面的两个A数组的拼接体求最大子数组和即可。易得这种情况的答案：maxSubArrSum(AA)

思路清楚了吧？下面直接上代码，可以直接秒：

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

class Solution {
public:
    int kConcatenationMaxSum(vector<int> &arr, int k) {
        //先求和
        ll sum = 0;
        for (auto x: arr) sum += x;
        //1.先特判k=1
        if (k == 1) {
            //相当于对A求最大子数组和
            int n = arr.size();
            vector<ll> dp(n);
            dp[0] = arr[0];
            for (int i = 1; i < n; i++) {
                dp[i] = max(dp[i - 1], 0LL) + arr[i];
            }
            ll res = 0;
            for (auto x: dp) res = max(res, x);
            return res%MOD;
        }
        //2.再处理k>=2的情况
        auto arr2 = arr;
        arr.insert(arr.end(), arr2.begin(), arr2.end()); //将数组拼接到它自己后面
        int n = arr.size();
        //下面就是正常的对AA求最大子数组和
        vector<ll> dp(n);
        dp[0] = arr[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i - 1], 0LL) + arr[i];
        }
        ll res = 0;
        for (auto x: dp) res = max(res, x);
        //下面分类讨论
        if (sum<=0) return res;
        return (sum*(k-2)+res)%MOD;
    }
};

本次题目讲解完毕！下一次，网格图dp见！