前言

本笔记是我挑战灵神的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见！

1.4 网格图DP 12月8日更新

1.4.1 简介

好的，同学们，可能是因为题目同质化比较严重，这次的刷题速度也是非常的快，8天刷了12道题目，所以这可能是我们算法笔记系列更新间隔最短的一次了。老样子，先看看我们的做题情况：

和之前一样，由于时间不足，我只会完成各个知识点的基础部分，不然我想这学期+寒假刷完dp就根本不可能了。

老样子，给题目分分类：

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

(例题-精讲)64. 最小路径和 Note:是二维dp的基础，会了这道题，下面很多题目就无师自通了(除了三维dp)

(讲解)62. 不同路径 Note:是不是对味了？和前面一样，网格图dp也能解决路径数量问题，只需要将取二者的极值变成二者简单相加即可

(讲解)63. 不同路径 II Note:只要会做上面的62题，这题只需要额外判断候选的两个格子不是障碍物格子就能做出来

120. 三角形最小路径和 Note:特判一下边界防止越界即可，其它和64题一模一样

931. 下降路径最小和 1573 Note:特判一下边界防止越界即可，其它和64题一模一样

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

3603. 交替方向的最小路径代价 II 1639 Note:这个奇数秒偶数秒就是唬人的，看一眼用例就知道了，只要会做64题，纵使计费方式有变化，跟着题目的意思来就能解出来

1289. 下降路径最小和 II 1697 Note:算是64题的移动方式的扩充版，需要再开一层循环来寻找上一层的最小和，来继承下去，使得全局解最优

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

(讲解)3393. 统计异或值为给定值的路径数目 1573 Note:三维dp，难度上来了一些，如果这题会做，那么这一板块三维dp的其它题目就无师自通了

(讲解)2684. 矩阵中移动的最大次数 1626 Note:需要从行优先遍历改成列优先遍历，并且判断条件更复杂，比较有难度

2304. 网格中的最小路径代价 1658 Note:计费条件比较新颖，需要开循环预先计算移动过来后的花费后取最小，比较复杂，有难度

3742. 网格中得分最大的路径 1804 Note:是比较有难度的三维dp，和下面的3418类似，但是逻辑上简单一些

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

(讲解)3418. 机器人可以获得的最大金币数 1798 Note:这是这一板块知识中最难的题目，由于我们有两次感化的机会，我们就需要考虑如何使用这两次机会才是最优解。如果在某个单元格遇到了强盗，我们需要同时考虑硬接伤害还是感化强盗两种情况，还得分别取最大值，逻辑比较复杂

这次要讲解的题目也是非常非常的多啊，达到了6道题目！不多说，下面我们直接开讲！

1.4.2 开始讲解

首先我们来讲第一题：64. 最小路径和，这是作为例题精讲的题目，先看题。

首先，读完题目之后，是不是第一反应是感觉和bfs有点像？但是bfs只能找最短路径，没法找出路径上总和最小的路径——它不具备记录路径信息的能力。

那么dfs是不是可以？配合数组可以直接回溯路径，这样，我把每个路径都记录下来，不就能得出最小路径和了吗？

数据量小的时候，当然可以。但是，一旦数据量大，假设从左上角到右下角有100000条路径，dfs会傻傻的全都走一遍，而且还会走不少重复的路径，然后累加出每条路径之和，实在是太慢了。

所以，下面我们就要和上面一样，从记忆化搜索，再到递推。

先从记忆化搜索开始吧。可以先看一下下面的图片。为了配合图片，我把题目的示例摘过来：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

PS：下面文字摘自灵神题解。

见微知著，想清楚最后一步发生了什么，就想清楚每一步发生了什么。

受上图启发，定义 dfs(i,j) 表示从左上角到第 i 行第 j 列这个格子（记作 (i,j)）的最小价值和。

分类讨论怎么到达 (i,j)：

如果是从左边过来，那么必须先到达 (i,j−1)，我们需要知道从左上角到 (i,j−1) 的最小价值和，再加上 gird[i][j]，得到 dfs(i,j−1)+grid[i][j]。
如果是从上边过来，那么必须先到达 (i−1,j)，我们需要知道从左上角到 (i−1,j) 的最小价值和，再加上 gird[i][j]，得到 dfs(i−1,j)+grid[i][j]。
二者取最小值，得到状态转移方程：

$$ dfs(i,j)=min(dfs(i,j−1),dfs(i−1,j))+grid[i][j] $$

有了这个方程之后，是不是可以直接写出记忆化搜索的代码了？

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector<int>(n, -1)); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0 || j < 0) {
                return INT_MAX;
            }
            if (i == 0 && j == 0) {
                return grid[i][j];
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            return res = min(dfs(i, j - 1), dfs(i - 1, j)) + grid[i][j];
        };
        return dfs(m - 1, n - 1);
    }
};

下面，我们尝试将它1:1翻译成递推。

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，f[i+1][j+1] 的定义和 dfs(i,j) 的定义是一样的，都表示从左上角到第 i 行第 j 列这个格子（记作 (i,j)）的最小价值和。这里 +1 是为了把 dfs(−1,j) 和 dfs(i,−1) 这些状态也翻译过来，这样我们可以把 f[0][j] 和f[i][0]作为初始值。

相应的递推式（状态转移方程）也和 dfs 一样：

$$ f[i+1][j+1]=min(f[i+1][j],f[i][j+1])+grid[i][j] $$

问：为什么 grid[i][j]的下标不用变？

答：既然是在 f 的最左边和最上边插入一排状态，那么就只需要修改和 f 有关的下标，其余任何逻辑都无需修改。或者说，如果把 grid[i][j] 也改成 grid[i+1][j+1]，那么当 i=m−1 或者 j=n−1 时 grid[i+1][j+1] 会下标越界，这显然是错误的。

初始值：

f[0][j]=f[i][0]=∞，翻译自递归边界 dfs(−1,j)=dfs(i,−1)=∞。
f[1][1]=grid[0][0]，翻译自递归边界 dfs(0,0)=grid[0][0]。
答案为 f[m][n]，翻译自递归入口 dfs(m−1,n−1)。

代码是这样的：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector f(m + 1, vector<int>(n + 1, INT_MAX));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[1][1] = grid[i][j];
                } else {
                    f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + grid[i][j];
                }
            }
        }
        return f[m][n];
    }
};

看到这里，你应该掌握了这道题目了。只要你掌握了这道题目的基本做法，下面的很多题目就都能做了。

接着我们来看第二题：62. 不同路径，先看题。

我们可以看出它和上面64题的差别：它求的是路径数量。我们回到64题的转移方程：

$$ f[i+1][j+1]=min(f[i+1][j],f[i][j+1])+grid[i][j] $$

可以发现，它为了使得最终结果是最小的，在考虑每一个格子时，选择继承它上方和左边两个格子值最小的那一方。

但是我们是计算路径，我们的dp数组的每个格子里面填写的应该是从起点到当前格子的路径总数，并不需要考虑谁大谁小，所以，直接把到左边格子的路径数量和到上面格子的路径数量加起来就行了，得到如下转移方程：

$$ f[i+1][j+1] = f[i+1][j]+f[i][j+1] $$

那么我们该如何初始化f[1][1]呢？由于起点就是站着不动，所以从起点到起点只有1条路径数量，即f[1][1]=1。想想也不可能是0啊，因为起点是万物起源，如果写0，这样转移之后其他格子的值就依然都是0，也不合常理。

知道了这个思路后，代码就很好写了，把转移方程往里面一套就行了：

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

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0 && j==0) {
                    dp[1][1]=1;
                } else {
                    dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1];
                }
            }
        }
        return dp[m][n];
    }
};

接着我们来看第三题：63. 不同路径 II，先看题。

这题的基本逻辑和上面这道题是一样的，就是多了一套障碍物判断的逻辑。

逻辑的写法有两种：一种是直接判断当前单元格是否为障碍物格子，如果是则保持值为0，防止其干扰路径计算；

另一种是判断左边和上面的单元格是否为障碍物格子，只有不是才会将其路径累加到当前单元格上。

当然，为了代码的健壮性，你也可以双管齐下——都判断，但是没啥必要。

我的代码选择的是第二种写法：

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

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(),n=obstacleGrid[0].size();
        if (obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) return 0;
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0 && j==0) {
                    dp[1][1]=1;
                }else {
                    if (i>0 && obstacleGrid[i-1][j]==0) {
                        dp[i+1][j+1]+=dp[i][j+1];
                    }
                    if (j>0 && obstacleGrid[i][j-1]==0) {
                        dp[i+1][j+1]+=dp[i+1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

那么肯定会有同学问了：如果我当前单元格是障碍物单元格咋办？

没事啊，我的路径数量正常累加在这个障碍物单元格上，但是它没法干扰别的单元格的路径数量计算：因为这个格子会在别的单元格判断左边/上面的格子是否为障碍物格子时被pass掉。并且，我已经在程序的开头通过特判排除掉了起点或者终点是障碍物单元格的情况。

所以，可能就是程序执行慢了一丢丢——多做了加法运算，别的没有任何影响。

第一种情况也同理，障碍物格子的路径数量，由于初始值为0，又访问不到，所以根本干扰不了路径计算。

接着，我们来看第四题：3393. 统计异或值为给定值的路径数目，先看题，开始上强度了。

上面的三道题全都是二维dp，而这道题需要用到三维dp了。为什么呢？(下方文字改编自Gemini 3 Pro，因为我觉得讲的比我好)

先看看为何第二题能用二维dp：因为在这个问题里，当我们在 (i, j) 这个点时，我们 不在乎 之前是怎么走过来的，走了哪些格子，数字是多少。只要能到达 (i, j)，它对后续走到终点的贡献都是一样的（只是作为一条有效路径继续延伸）。之前的历史信息（路径的具体内容）对于“下一步怎么走”或者“最终目标”没有影响，只有“到达这里”这个事实有意义。 这就是所谓的无后效性。

现在题目要求：路径上的异或和必须等于 k。

如果我们强行沿用二维定义：

dp[i][j] = 从 (0, 0) 走到 (i, j) 且满足异或和要求的路径数量？

这行不通。因为你还没走到终点，你不知道当前的异或和是多少，也无法预知走到终点时能不能凑成 k。

如果我们换个定义：

dp[i][j] = 从 (0, 0) 走到 (i, j) 的路径数量。

当我们计算 dp[i][j] 时，我们需要从 dp[i-1][j]（上方）和 dp[i][j-1]（左方）转移过来。 假设 grid[i][j] 的值是 x。

• 上方点 (i-1, j)可能有 10 条路径到达。但这 10 条路径的异或和可能各不相同。

  • 有的路径异或和是 1，走到 (i, j) 后变成 1 ^ x。
  • 有的路径异或和是 5，走到 (i, j) 后变成 5 ^ x。
• 如果我们在 dp[i-1][j] 里只存了一个数字“10”（表示有10条路径），我们就彻底丢失了这 10 条路径各自的异或和信息。
• 没有这些信息，当你走到终点 (m-1, n-1) 时，你只能告诉我有多少条路径到了终点，却无法分辨哪条路径的异或和是 k。

本质原因： 动态规划的本质是将“历史信息”压缩到“状态”中。 在普通路径问题中，历史信息只需要“我到了 (i, j)”就足够了。 在本题中，历史信息不仅包含“我到了 (i, j)”，还必须包含 “我目前的路径异或和是多少”。因为这个数值直接决定了这条路径未来是否符合条件。

所以，为了区分到达同一个格子 (i, j) 但 异或和不同 的路径，我们需要把“当前的异或和”也作为一个状态维度存下来。

正确的状态定义：

dp[i][j][v] = 从 (0, 0) 走到 (i, j)，且路径异或和恰好为 v 的路径数量。

• i: 行号 (0 到 m-1)
• j: 列号 (0 到 n-1)
• v: 当前路径的异或值 (题目提示 grid 值和 k 都小于 16，意味着异或和最大也就 0-15 之间，非常小，适合做维度)

转移方程： 要想走到 (i, j) 且异或和为 v，那么上一步（比如从上方 (i-1, j) 走来）的异或和必须是 u，使得 u ^ grid[i][j] = v。根据异或性质，这意味着 u = v ^ grid[i][j]。

所以： dp[i][j][v] = dp[i-1][j][v ^ grid[i][j]] + dp[i][j-1][v ^ grid[i][j]] (需注意边界条件)

最终答案： dp[m-1][n-1][k] 即：走到终点，且异或和恰好等于 k 的路径数。

思路讲完了，下面看代码：

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

class Solution {
public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        int n = grid.size(),m = grid[0].size();
        vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(m+1,vector<ll>(16)));
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (i==0 && j==0) {
                    dp[1][1][grid[0][0]]=1;
                }else {
                    for (int u=0;u<16;u++) { //遍历题目指定的可能的16种异或值
                        dp[i+1][j+1][u]=(dp[i+1][j][u^grid[i][j]]+dp[i][j+1][u^grid[i][j]])%MOD;
                        //这个方程是怎么出来的呢？感觉一头雾水。没事，下面会讲！
                    }
                }
            }
        }
        return dp[n][m][k]%MOD;
    }
};

那么这一句转移方程是怎么出来的呢？其实是利用了异或运算的一个小性质(我也不知道哈哈哈)：

$$ 如果 A \oplus B = C，那么 A = C \oplus B $$

那我们该如何利用这个性质呢？

我们现在的目标是：在 (i, j) 这个位置凑出异或和 v。
现在的格子上的数值是 grid[i][j]。

这就好比一个算术题：

$$ \text{之前的异或和} \oplus \text{当前格子的值} = \text{目标异或和 } v $$

即：

$$ \text{PrevSum} \oplus \text{grid}[i][j] = v $$

根据上面的性质，在上一个格子（无论是上面还是左边），它的异或和必须是：

$$ \text{PrevSum} = v \oplus \text{grid}[i][j] $$

所以，总结成方程，就是：

现在的路径总数 = (从上面下来凑出 v 的路径数) + (从左边过来凑出 v 的路径数)

即：

$$ dp[i][j][v] = dp[i-1][j][\underbrace{v \oplus \text{grid}[i][j]}_{\text{需要的上一步状态}}] + dp[i][j-1][\underbrace{v \oplus \text{grid}[i][j]}_{\text{需要的上一步状态}}] $$

这下子应该很清晰明了了。

啃完上面这块硬骨头，我们来看第五题：2684. 矩阵中移动的最大次数，先看题，难度会比上面一题缓和一些。

看完题目，我们能很容易发现，这个题目的逻辑是一列一列来的，所以我们需要把之前的行优先遍历在这里改成列优先遍历。

先看看怎么初始化：第一列一定是都可达的，毕竟是起点，所以全部初始化为true。

再看看能够继承的单元格有哪些：(row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1)，相当于是左边，左上角和左下角。这样，就有越界的风险，需要分类讨论了。

然后我们还需要考虑一个问题：它需要连着往右移动，只要中间断了一格，后面就一定连不上了。我的第一反应是用二维dp来存储走了的步数，后面感觉好像没必要，只需要存储是否到达过这个格子就行了，至于走了几步？到第几列就是走了几步，无非就是减不减一的事情。

那么如何处理状态转移呢？我们可以这么思考：左上、左下、左边的单元格，只要有一个满足数字严格小于当前单元格，并且本身是可到达的，那么当前单元格就是可到达的。

然后呢，也可以优化一下程序本身：如果这一列的格子全都到不了，那就直接退出，防止出现第二列已经全部不可达，结果程序还傻傻跑完剩下的998列的情况。

思路就这些，看代码，有注释：

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // dp[i][j] 表示：是否能到达坐标 (i, j)
        // 实际上我们不需要存具体的步数，因为到达第 j 列，步数一定是 j
        vector<vector<bool>> dp(m, vector<bool>(n, false));
  
        int ans = 0;

        // 初始化：第一列所有位置都是起跑线，默认可达
        for (int i = 0; i < m; i++) {
            dp[i][0] = true;
        }

        // 开始遍历，注意：外层遍历列（也就是步数），内层遍历行
        for (int j = 1; j < n; j++) { // j 代表列 (current col)
            bool can_reach_any = false; // 剪枝标记：这一列有没有任何一个点能走到？
  
            for (int i = 0; i < m; i++) { // i 代表行 (current row)
                // 检查三个来源：左上(i-1, j-1)，左(i, j-1)，左下(i+1, j-1)
                // 条件：1. 来源格子必须在矩阵内 2. 来源格子必须是"可达"的 3. 当前值严格大于来源值
  
                bool from_left_up = (i > 0 && dp[i-1][j-1] && grid[i][j] > grid[i-1][j-1]);
                bool from_left      = (dp[i][j-1] && grid[i][j] > grid[i][j-1]);
                bool from_left_down = (i < m - 1 && dp[i+1][j-1] && grid[i][j] > grid[i+1][j-1]);

                if (from_left_up || from_left || from_left_down) {
                    dp[i][j] = true;
                    can_reach_any = true;
                    ans = j; // 只要能到达第 j 列，最大步数就是 j
                }
            }
  
            // 剪枝：如果这一列全是 false，后面就不用看了，肯定过不去
            if (!can_reach_any) break;
        }
  
        return ans;
    }
};

最后的最后，我们终于到达了第六题：3418. 机器人可以获得的最大金币数，这是这一波最难的题目，先看题。

由于我们引入了感化次数的概念，这样我们在dp传递的过程中就需要记录感化次数的使用情况，所以本题和第4题类似，是三维dp。

先看看怎么初始化数组的值。题目说了，金币的值可以是负数，所以我们肯定不能用0来初始化，因为这样会导致下面状态转移使用max对比时，错误的把0取过来(也就是这个单元格尚未访问到，反而还干扰了运算)。所以，由于我们找的是最大值，为了避免干扰，那就把初始值取最小，这里我选择取-2e9，远远小于题目的最小值-10^6，很安全。

接下来讲讲如何状态转移。我们需要分类讨论一下coins[i][j]：

如果coins[i][j]的值是正数，那就不用管，直接把前面的用了相同感化次数的格子的总金币数1:1继承过来就行，转移方程如下(k为感化的使用次数)：

$$ dp[i+1][j+1][k] = max(dp[i+1][j][k],dp[i][j+1][k])+coins[i][j]\space(k=0,1,2) $$

当然呢，也不能无脑继承，因为如果左边和上面的格子全都没初始化，也就是它们的值都是-2e9，直接把它和金币相加放入当前dp单元格，会出问题。所以再加一个判断即可：

for (int k=0;k<=2;k++) {
    int prev = max(dp[i+1][j][k],dp[i][j+1][k]);
    if (prev>-2e9) dp[i+1][j+1][k] = prev+coins[i][j];
}

接着我们来讲coins[i][j]的值是负数，也就是会被强盗抢abs(coins[i][j])数量金币的情况。这个时候，我们除了要从左边和上面选一个，我们还得面临要不要在这个格子用感化机会的抉择。

有的同学可能会想：贪心思想，如果机会还有那就用呗。这样想想也是错的吧，我肯定优先把机会用在被偷的金额最大的那两次才是最好的，如果开局偷一两个金币的时候就直接把两次机会都用了，后面偷一二十个金币的时候就没得用了，最终结果肯定不是最大的。

所以，我们需要同时讨论这2*2=4种情况。

思路很简单，先尝试不感化，硬接伤害；再尝试感化，并在感化次数相同的前提下取感化与不感化的最大值。

代码如下：

for (int k=0;k<=2;k++) {
    //先试试不感化
    int prevSameK=max(dp[i][j+1][k],dp[i+1][j][k]);
    if (prevSameK>-2e9) {
        dp[i+1][j+1][k] = prevSameK+coins[i][j];
    }
    //再感化
    if (k>0) {
        int prevLowerK = max(dp[i][j+1][k-1],dp[i+1][j][k-1]);
        if (prevLowerK>-2e9) {
            dp[i+1][j+1][k] = max(dp[i+1][j+1][k],prevLowerK);
        }
    }
}

解释一下：上面的不感化相当于继承左边和上面两个使用了相应感化次数的格子的最大值，然后再硬接伤害，扣除对应金币；下面的感化相当于直接继承k-1次感化次数格子的值(注意，感化并不是化负为正，而是使金币免于被扣除)。

然后我们在感化和不感化时都考虑了接左边格子还是上面格子的情况，所以相当于就考虑了4种情况，非常全面。

思路已经讲完，完整代码如下：

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

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size(),n = coins[0].size();
        vector<vector<vector<int>>> dp(m+1,vector<vector<int>>(n+1,vector<int>(3,-2e9)));
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0 && j==0) {
                    dp[1][1][0]=coins[0][0];
                    if (coins[0][0]<0) dp[1][1][1]=0;
                }else {
                    if (coins[i][j]>0) {
                        for (int k=0;k<=2;k++) {
                            int prev = max(dp[i+1][j][k],dp[i][j+1][k]);
                            if (prev>-2e9) dp[i+1][j+1][k] = prev+coins[i][j];
                        }
                    }else {
                        for (int k=0;k<=2;k++) {
                            //先试试不感化
                            int prevSameK=max(dp[i][j+1][k],dp[i+1][j][k]);
                            if (prevSameK>-2e9) {
                                dp[i+1][j+1][k] = prevSameK+coins[i][j];
                            }
                            //再感化
                            if (k>0) {
                                int prevLowerK = max(dp[i][j+1][k-1],dp[i+1][j][k-1]);
                                if (prevLowerK>-2e9) {
                                    dp[i+1][j+1][k] = max(dp[i+1][j+1][k],prevLowerK);
                                }
                            }
                        }
                    }
                }
            }
        }
        return max({dp[m][n][0],dp[m][n][1],dp[m][n][2]});
    }
};

好了，历经3天的时间，我终于写完了这次算法笔记。下一次，背包问题见！

1.5 背包问题

1.5.1 0-1背包问题 251215更新

简介

由于这一系列的题目不多，所以时隔仅仅6天，我又来更新了。

先讲讲啥是0-1背包问题吧：每个物品只能选一次，即要么选，要么不选。

这是你必须掌握的东西，因为你需要靠这个东西来区分各种题型。

老样子，看看本次做题情况：

这次的题目虽然不难，但是花样变的非常快，题目的马甲特别难脱。

我做起来的感觉是这样的：第一题，由于太久没做01背包问题了，就忘记咋做了，看了题解，会做了，就ac了第一题；接着去看第二题，我去，怎么又不会了，于是又去看题解。。。

这就导致这5道题目我全都看了题解才会写，我真的没招了。。。

但是呢，每道题目的题解看完之后，我都有一种豁然开朗的感觉——题解还是比较好理解的，所以这5道题目，我的难度总体都会划到中等。

但是呢，老样子的分类依然不能丢：

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

无(全看题解去了，我真服了)

2.进阶题(我需要被提示一下，并且思考一下才能做出来)

(例题-精讲)416. 分割等和子集 Note:这是这一系列题目，算是马甲比较薄的一道题了，算是经典的"拿与不拿"的01背包问题

(讲解)494. 目标和 Note:马甲第一眼很难看出来，重点讲怎么拆马甲，很像数学推导的过程

(讲解)2915. 和为目标值的最长子序列的长度 1659 Note:有点类似之前的最大连续子序列的思想，考虑不拿这个和拿这个接上的长度的最大值

3.困难题(需要看题解并理解后才能做出来)

2787. 将一个数字表示成幂的和的方案数 1818 Note:需要想到提前制作"商品"，后面思路就很顺，经典的01背包问题

(讲解)3180. 执行操作可获得的最大总奖励 I 1849 Note:需要想到提前排序并且转移条件多了一个，应该是最难的

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

无

那么话不多说，我们直接开始讲解！

开始讲解！

首先我们来看第一题：416. 分割等和子集，先看题。

看完题之后，我的第一反应是一头雾水：这道题和01背包dp有啥关系吗？

后来看了一眼题解才发现，我需要把题目条件转换一下：分隔成两个和相等的子集，不就是我需要从中选出一些数，使它们的和等于总和的一半吗？

所以，思路很清晰了，我们首先需要计算一下这个数组的和，补充个冷知识，使用cpp的reduce(vet.begin(),vet.end())就能很好的做到这一点，以前我都是用循环手搓的。

然后呢，显而易见的特判是：如果这个数组的和是奇数，那说明它一定是没法做到和等于总和的一半的——因为一半本就不存在。所以这种情况我们在代码的最上面就能直接处理掉。

接着就是和为偶数的一般情况了。此时我们就需要运用到0-1背包dp的知识了。先来讲讲啥是01背包dp：

01背包问题是动态规划中最经典的问题之一。

核心原理

01背包问题的核心在于决策：对于每一个物品，我们只有两种选择：

1. 放入背包（1）。
2. 不放入背包（0）。

我们要做的就是在一系列物品中做出这些“是/否”的选择，以确保在不超过背包容量的前提下，使放入的物品的总价值最大。

动态规划（DP）用法与状态定义

动态规划通过定义一个状态数组（DP表）来存储子问题的最优解，然后利用这些子问题的解来推导出更大问题的解。

1. 状态定义

我们通常使用一个二维数组 dp[i][j] 来定义状态：

• i：表示当前考虑前 i 个物品（从第1个到第 i 个）。
• j：表示当前背包的容量是 j。
• dp[i][j]：表示在前 i 个物品中选择，且背包容量为 j 时，能达到的最大总价值。

2. 初始条件

• dp[0][j] = 0：没有物品可选时，最大价值为0。
• dp[i][0] = 0：背包容量为0时，最大价值为0。

📜 递推公式（状态转移方程）

假设第 i 个物品的重量为 w_i，价值为 v_i。在计算 dp[i][j] 时，我们基于对第 i 个物品的选择进行分类讨论：

情况一：不选第 i 个物品

此时，最大价值等于考虑前 i-1 个物品、容量仍为 j 时的最大价值。

$$ \text{价值} = dp[i-1][j] $$

情况二：选择第 i 个物品

只有当背包容量 j 大于或等于第 i 个物品的重量 $w_i$ 时，才能选择它。

• 剩余容量： 放入 w_i 后，背包剩余的容量为

  $$ j - w_i $$

• 剩余价值： 剩余容量的最大价值为

  $$ dp[i-1][j - w_i] $$

  （因为第 i 个物品已经放入，所以我们只看前 i-1 个物品）。

• 总价值：

  $$ \text{剩余价值} + \text{物品 } i \text{ 的价值} = dp[i-1][j - w_i] + v_i $$

$$ \text{价值} = dp[i-1][j - w_i] + v_i \quad (\text{当 } j \ge w_i \text{ 时}) $$

3. 最终递推公式

dp[i][j]就是这两种情况下的最大值：

$$ \text{当 } j < w_i \text{ 时（容量不足以放第 } i \text{ 个物品）：}dp[i][j] = dp[i-1][j] $$

$$ \text{当 } j \ge w_i \text{ 时（容量足够）：}dp[i][j] = \max( \underbrace{dp[i-1][j]}_{\text{不选第 } i \text{ 个物品}}, \underbrace{dp[i-1][j - w_i] + v_i}_{\text{选择第 } i \text{ 个物品}} ) $$

看完了吧？这一系列题目的核心思想其实就是上面这一套理论。

为了让这套理论服务于这道题目，我们需要研究一下如何将上面的当前总价值dp[i][j]和当前总重量j套到这道题目上。

首先我们提取一下这道题目的题干和我们上面转化出来的关键结论："判断是否可以"，"和等于总和的一半"。

那么，我们可以将前者与上面的总价值对应上，使用bool类型，即dp[i][j]表示：从上一步递推到我这一步总和能否达到j，也就是后者相当于就是和j。

一步步往后递推，最后我们就可以在dp[m][n]获取到和能否凑成n的信息了。

讲解完毕，代码如下：

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //1.先计算nums之和sum
        int sum = reduce(nums.begin(), nums.end());
        if (sum%2!=0) return false; //如果和为奇数直接特判不可行
        sum/=2;
        //2.开始dp
        int n = nums.size();
        vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
        dp[0][0]=true;
        for (int i=0;i<n;i++) {
            int x = nums[i];
            for (int j=0;j<=sum;j++) {
                dp[i+1][j] = dp[i][j] || (j >= x && dp[i][j-x]);
                //这一步需要讲解一下：从上一步到这一步的和能凑成j的条件是，要么不选这个，直接继承上一步和为j的状态即可；
                //要么选这个，但是需要满足j-x>=0(否则会越界)，然后如果从上上步到上一步和能凑到j-x，那这一步一定能凑到j-x+x=j
                //二者只需要满足其一，就说明在这一步能凑到j，若都不满足则不行
            }
        }
        return dp[n][sum];
    }
};

好的，接着我们来看第二题：494. 目标和 ，先看题。

这题是马甲拆除题。首先，添加加号减号的本质，其实就是把数分成了两类：一类是加加号的数，一类是加减号的数。

然后呢，如果你想求加减运算后的结果，除了直接算，其实还有一个更直接的方法，这里我偷个懒，直接把灵神的题解截过来：

那么大家肯定就很好奇了：为啥给target套个绝对值然后一算，就是最优背包容量了？

本质其实就是让背包容量尽量小。通过上面p和q的对比以及分类讨论，你会发现只要套个绝对值，无论target本身是正还是负，就自动取了背包容量最小的那一份。

容量取好了之后，后面的问题就转换成了："我怎么从 [1, 2, 3, 4, 5] 里挑几个数，填满容量为 6 的背包？"

下面的步骤，就不需要我多说了吧。上代码：

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

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int S = reduce(nums.begin(), nums.end());
        int s = S - abs(target);
        if (s%2==1 || s<0) return 0;
        int n = nums.size(),c = s/2;
        vector dp(n+1,vector<int>(c+1));
        dp[0][0]=1;
        for (int i=0;i<n;i++) {
            int x = nums[i];
            for (int j=0;j<=c;j++) {
                if (j<x) {
                    dp[i+1][j] = dp[i][j];
                } else {
                    dp[i+1][j] = dp[i][j]+dp[i][j-x];
                }
            }
        }
        return dp[n][c];
    }
};

接着我们来看第三题：2915. 和为目标值的最长子序列的长度，先看题。

这一题和上面两题的类型不太一样，已经进入了求最值的范畴。继续套用上面的01背包模型，读完题目之后，我们能知道，此时的背包容量其实就是子序列的和，而物品价值其实就是子序列的长度。

由于是求最大值，我们只需要考虑继续把当前元素接上的长度更大还是不接当前元素，直接继承上一步相同长度的值的长度更大。

只需要小小修改一下递推逻辑即可，其他逻辑是一模一样的。

上代码：

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

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> dp(n+1,vector<int>(target+1,-INT_MAX));
        dp[0][0] = 0;
        for (int i=0;i<n;i++) {
            int x = nums[i];
            for (int j=0;j<=target;j++) {
                if (j<x) dp[i+1][j] = dp[i][j]; //如果j-x<0会越界，所以此时只能继承，没法接上
                else dp[i+1][j] = max(dp[i][j],dp[i][j-x]+1);
            }
        }
        if (dp[n][target]>0) return dp[n][target];
        return -1;
    }
};

最后啊，终于，我们来到了第四题：3180. 执行操作可获得的最大总奖励 I，先看题。

首先，读完题目后，我们能发现，这题需要rewardValues[i] 大于 你当前的总奖励 x，才能将 rewardValues[i] 加到 x 上。

首先，从贪心的思想，由于数字全是正数，所以取的数字越多肯定总和最大。那么，我们就有先将这个rewardValues 升序排序的想法，这样，从小的数取起，后面的数就更容易比当前总和大。

所以，我们完成了第一步，就是给这个rewardValues排序。

然后呢，第二步就是将上面01背包模型的两个重要变量：当前总价值(dp[i][j])和当前总重量(j)套在这道题目上。

先看看下面表格的对比吧：

但是呢，我们好像又发现，如果直接按照表格来，那岂不是dp[i][j]=j...这样不是怪怪的吗？我说白了，我白说了。

所以呢，当重量 == 价值时，我们不再关心“在这个容量下价值是多少”（因为已知是容量本身），我们只关心“这个容量（总分）能不能凑出来”。

那么，就这样愉快的决定吧：将dp[i][j]设置为bool类型，将背包容量与重量对应，从而形成和第一题类似的01dp变种问题，只不过这一题的马甲会比第一题厚很多。

既然已经确定了该怎么dp，那我们来研究一下这个"无限背包"的背包容量吧。已知题目用例范围：1 <= rewardValues[i] <= 2000，也就是，只有你鬼使神差的把总和凑到了1999，它才能再加2000，达到了3999这个最大值，也就是上面表格所提到的2*v-1。所以背包容量在当前题目设置成4000及以上是非常安全，完全够用的。从理论上来说，确实是无底洞——但是题目的用例是有上限的。

到这里，我们就完成了最重要的第二步——确定了该进行怎么样的dp，并且把背包容量都定好了。

接着我们来做第三步，就是研究递推的逻辑。这个倒也没啥好多说的，和第一题的递推逻辑差不多，多加一条j-x<x的逻辑就行了。

最后呢，在推完之后，我们还有一步，也就是第四步：寻找dp数组最后一行值最大的能凑成的j。千万不要万事大吉直接无脑dp[m][n]，这题并不保证用例一定能取到3999，而且题目也要求的是最大值。所以我们需要遍历一下dp数组的最后一行，找出最大的dp[i][j]为true的下标，就是题目答案。

逻辑很清晰了，上代码(注释是Gemini 3 Pro写的哈哈哈，看完了还看不懂的是这个)：

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

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        // ==========================================
        // 第一步：贪心思想的预处理
        // ==========================================
        // 为什么要排序？
        // 题目限制：只有当 "当前总分 x < 当前物品值 v" 时，才能捡起 v。
        // 为了获得最大奖励，我们应该先捡小的，慢慢把 x 垫高，
        // 这样后面遇到大的奖励时，x 虽然变大了，但只要还小于那个大奖励，就能继续捡。
        // 如果先捡大的，x 一下子变得很大，小的就再也捡不起来了。
        sort(rewardValues.begin(), rewardValues.end());

        // ==========================================
        // 第二步：定义 DP 状态与范围
        // ==========================================
        // n: 物品数量
        // s: 背包容量上限。
        // 为什么是 4000？
        // 题目给的数据范围是 rewardValues[i] <= 2000。
        // 假设最后一个捡起的物品是 max_v (比如 2000)，
        // 捡起它之前，手中总分必须 < 2000 (最大是 1999)。
        // 捡起它之后，总分最大可能为 1999 + 2000 = 3999。
        // 所以 4000 足够覆盖所有可能的结果。
        int n = rewardValues.size();
        int s = 4000; 

        // dp[i][j] 的含义 (Bool 类型 DP)：
        // "只考虑前 i 个物品，是否能恰好凑出总奖励 j？"
        // true = 能凑出；false = 凑不出
        // 这里不再存 int 价值，因为下标 j 本身就是价值。
        vector<vector<bool>> dp(n + 1, vector<bool>(s + 1, false));

        // 初始化：
        // 前 0 个物品，凑出总分 0 是必然可以的（什么都不拿）。
        dp[0][0] = true;

        // ==========================================
        // 第三步：状态转移 (核心逻辑)
        // ==========================================
        for (int i = 0; i < n; i++) {
            int x = rewardValues[i]; // 当前准备考虑放入背包的物品（奖励）
    
            for (int j = 0; j <= s; j++) {
                // 情况 1：不选当前物品 x
                // 如果前 i 个物品能凑出 j，那前 i+1 个物品肯定也能凑出 j。
                // 直接继承上一行的结果。
                dp[i+1][j] = dp[i][j];

                // 情况 2：尝试选当前物品 x
                // 这里有三个条件必须同时满足：
                // 1. (j >= x): 数组下标保护，要凑的目标分 j 肯定得比物品 x 大。
                // 2. (j - x < x): 【题目的核心限制】
                //    j - x 代表"拿 x 之前的旧总分"。
                //    题目要求：旧总分必须小于当前物品值 x，才能拿 x。
                // 3. dp[i][j - x]: 【可达性检查】
                //    确保"拿 x 之前的旧总分"是前 i 个物品确实能凑出来的。
                if (j >= x && j - x < x && dp[i][j - x]) {
                    // 如果满足，说明 j 可以通过 "旧分(j-x) + 新物品(x)" 凑出来
                    dp[i+1][j] = true; 
                }
            }
        }

        // ==========================================
        // 第四步：输出结果
        // ==========================================
        // 遍历最后一行 DP 表（考虑了所有 n 个物品后）。
        // 找到标记为 true 的最大下标，那就是我们能获得的最大总奖励。
        int ans = 0;
        for (int j = 0; j <= s; j++) {
            if (dp[n][j]) {
                ans = j;
            }
        }
        return ans;
    }
};

好的！到这里，本次要讲解的题目就全部弄完了，下一次，还是背包问题，我们完全背包问题见！

1.5.2 完全背包问题 251218更新

简介

这次的题目非常少，只有3题(实则是因为我既没力扣会员，又只做基础题)，所以更新的比较快。

先看看本次做题情况：

本次题目总体难度不高，看了第一题的题解之后，后面两题都能自主完成。

这次就不划分难度了，因为全都是中等难度。看了一遍，感觉每道题都有可以讲的地方。下面咱们直接开讲。

开始讲解！

首先来看第一题：322. 零钱兑换，先看题。

其实呢，完全背包和0-1背包的区别本身就不大：后者是一类物品只能取一次，而前者是每一类物品可以无限制重复选。

对应的，转移方程的改变也很小。假设是传统的背包总重量有限，每个物品有不同重量和价值，问怎么拿能使价值最大化的传统问题。

我们来对比一下01背包和完全背包：

1. 核心定义

无论哪种背包，我们通常定义：

dp[i][j] 表示：在前 i 件物品中选择，放入容量为 j 的背包中，能获得的最大价值。

---

2. 01 背包：每件只有一个（选或不选）

01 背包的本质是：当前状态只依赖于“前一个物品”的状态。

转移方程

$$ dp[i][j] = \max(dp[i-1][j], \quad dp[i-1][j - w[i]] + v[i]) $$

逻辑拆解

当我们面对第 i 件物品时，只有两种决策：

1. 不拿第 i 件：那当前的价值就等于“前 i-1 件物品在容量 $j$ 下的最大价值”。即 dp[i-1][j]。
2. 拿第 i 件：前提是背包得装得下（j>=w[i]）。如果你决定拿它，你得给它腾出 w[i] 的空间。那么剩下的空间 j - w[i] 能装的最大价值是 dp[i-1][j - w[i]]。再加上这件物品的价值 v[i]。

空间优化（滚动数组）

面试和笔试最常考的是优化到一维：dp[j]。

• 代码：for j from C down to w[i] (逆序)
• 为什么逆序？ 因为我们在算 dp[j] 时，需要用到“上一层”的 dp[j - w[i]]。如果正序，dp[j - w[i]] 可能在这一层已经被更新过了（变成了拿过第 i 件物品后的状态），这就违反了 01 背包“每件只拿一次”的原则。

---

3. 完全背包：每件有无限个

完全背包的本质是：当前状态可以依赖于“当前物品”已经更新过的状态。

转移方程

注意看，这里和 01 背包只有一个字符的区别：

$$ dp[i][j] = \max(dp[i-1][j], \quad \mathbf{dp[i]}[j - w[i]] + v[i]) $$

(注意加粗部分是 i 而不是 i-1)

逻辑拆解

1. 不拿第 i 件：同上，dp[i-1][j]。

2. 拿第 i 件：既然可以无限拿，那么当你拿了一件第 i 项物品后，你依然可以从“包含了第 i 项物品选择方案”的状态中继续转移。

   • 通俗点说：拿了一件，我还可以再拿一件。所以参考的是 dp[i][j - w[i]]，这个状态可能已经包含了 1 个、2 个甚至更多个第 i 物品。

空间优化

• 代码：for j from w[i] up to C (正序)
• 为什么正序？ 这正是完全背包的精妙之处。正序更新意味着当你计算 dp[j] 时，用到的 dp[j - w[i]] 是这一轮（第 $i$ 轮）已经更新过的值。这恰好模拟了“物品可以被多次放入”的过程。

---

4. 深度对比：01 vs 完全

为了帮你加深印象，我们对比一下这两个最容易混淆的点：

维度	01 背包 (One-shot)	完全背包 (Unlimited)
选择逻辑	拿了它，就得看前一个物品留下的烂摊子。	拿了它，我还可以看现在的我还能不能再拿。
二维方程	dp[i-1][j-w[i]] + v[i]	dp[i][j-w[i]] + v[i]
一维循环方向	逆序 (防止重复使用同一物品)	正序 (利用重复使用同一物品)
现实类比	抽奖，奖池里每样奖品只有一份。	自助餐，菜没了后厨马上会补。

知道了大体的转移方程之后，我们可以回到题目了。

抓关键词："最少的硬币个数"，"硬币数量无限"。说明这是完全背包问题，并且由于要求最少，所以我们知道，dp数组的初始值得取一个极大值，这里我们选INT_MAX。

然后我们能很快确定，背包容量是总金额amount。这样，dp数组的初始化就完成了。

最后，我们结合上面学到的转移方程，直接往里一套就完事：

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

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1,INT_MAX));
        dp[0][0]=0;
        for (int i=0;i<n;i++) {
            int x = coins[i];
            for (int j=0;j<=amount;j++) {
                dp[i+1][j] = dp[i][j]; //兜底
                if (j-x>=0 && dp[i+1][j-x]<INT_MAX) dp[i+1][j] = min(dp[i][j],dp[i+1][j-x]+1);
            }
        }
        if (dp[n][amount]<INT_MAX) return dp[n][amount];
        return -1;
    }
};

其中有一个要注意的点：如果j太小了，比x小，它就没法取当前硬币了。这时候，我们必须要继承上个硬币达到同样金额的长度，否则本单元格的值还是INT_MAX，会漏情况。

接着我们来看第二题：518. 零钱兑换 II，是第一题的续题，先看题。

看完题目，思路瞬间涌上来了——这题我会！从求最值的浪漫初见到求种数的瞬间转变，是DP的老演员了：只不过是将求极值变成"我两个都要"。

思路正确！所以，这题的转移方程很简单：dp[i+1][j]=dp[i][j]+dp[i+1][j-x]。

但是呢，也不能无脑执行这个转移方程，因为j-x是有可能小于0的，会导致越界。所以，换成一个更加精妙的结构就行了：先无脑把dp[i][j]加上，然后再判断j-x是否大于等于0，如果是再把dp[i+1][j-x]加上。

并且呢，题目还标明了："题目数据保证结果符合 32 位带符号整数"。我去，那不是就写完了吗？看代码：

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1,0));
        dp[0][0]=1;
        for (int i=0;i<n;i++) {
            int x = coins[i];
            for (int j=0;j<=amount;j++) {
                dp[i+1][j]+=dp[i][j];
                if (j-x>=0) dp[i+1][j]+=dp[i+1][j-x];
            }
        }
        return dp[n][amount];
    }
};

用例依旧是齐刷刷的过，舒服！然后点击提交：

Line 16: Char 39: runtime error: signed integer overflow: 27131803 + 2123074792 cannot be represented in type 'value_type' (aka 'int') (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:25:39

我真求你了。不是说好的题目数据保证结果不会爆int吗？

然后呢，我突然想起来前面的题目貌似有过类似的经历，并且解决方案很简单粗暴：检测到溢出，就不加了。具体是哪道题我记不清了。

抱着试一试的心态，我给if (j-x>=0) dp[i+1][j]+=dp[i+1][j-x];这句话改成了下面这样：

if (j-x>=0 && dp[i+1][j]<=INT_MAX-dp[i+1][j-x]) dp[i+1][j]+=dp[i+1][j-x];

我去，居然直接过了！但是一个疑问也在我心中产生：为啥这样不会影响我最终答案的正确性呢？

问了问gemini，一开始它还说我这个判断条件写着没用，后面在我的逼问下终于承认了。

一句话总结：因为题目保证结果不会爆int，然后呢，由于是种数，所以是越加越多的。既然结果都不爆，那参与结果运算的那些数肯定也不会爆。由此推出：那些爆int的递推步骤是无效运算，可以省略。

又学到了，哈哈。

最后，我们来看第三题：279. 完全平方数，先看题。

这题其实就一个值得讲的地方：预处理题目所要求的数据，生成可以无脑套完全背包模板的商品。

别的套路和第一题一模一样，就不赘述了，直接看代码，我把想说的都标在里面了：

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

class Solution {
public:
    int numSquares(int n) {
        //1.找范围
        int r = (int)sqrt(n)+1;
        //2.制造物品
        vector<int> goods;
        for (int i=1;i<=r;i++) {
            goods.emplace_back(i*i);
        }
        //提前制造商品还有一个好处，就是能很轻松的获取背包的范围，便于下面创建dp数组
        //3.开始dp
        vector<vector<int>> dp(r+1,vector<int>(n+1,INT_MAX));
        dp[0][0]=0;
        for (int i=0;i<r;i++) {
            int x = goods[i];
            for (int j=0;j<=n;j++) {
                if (j-x<0) dp[i+1][j] = dp[i][j];
                else dp[i+1][j] = min(dp[i][j],dp[i+1][j-x]+1);
            }
        }
        if (dp[r][n]<INT_MAX) return dp[r][n]; //题目没说会有无效数据，这句判断是为了维护健壮性
        return -1;
    }
};

1.5.3 分组背包问题 260104更新

简介

最近事情也是有些多，并且也开始期末复习了，再加上这次的三道题目难度都不低，并且我还要忙着推hot100。。。简直debuff叠满了好吧，所以虽然只有三道题目，但是还是时隔了半个月才更新。

老样子，来看看本次做题情况吧：

完成算是全完成了，但是呢，多多少少都有看题解或者AI修正代码，所以难度是不低的，我决定三题全讲，也还是不分类了哈哈。

开始讲解！

ok，直接来看第一题：1155. 掷骰子等于目标和的方法数，先看题。

从本质上来说，所有的背包问题都是一样的：想办法利用题目条件确定背包总容量，物品种类数以及单格数值的初始化。

首先明确一下dp数组的初始值：本题是方法数，所以dp数组的初始值为0。

然后再明确一下物品种类数量：就是骰子的数量。

接着明确背包的总容量：题目要求等于目标和的方法数，我们就需要凑到题目给的target，所以定背包容量为target+1，便于递推。

接下来，就是最后一步，确定递推逻辑。

根据我们前面做的题目的经验，到这个骰子并且总和凑到了这个数的总方法数，就是累加上一个骰子到这一个骰子，并且凑到了某个总和的两种路径的方法数。就像这样：dp[i+1][j] = dp[i][j]+dp[i][j-x]。

但是这道题不能这样写。因为骰子最小的点数是1，并且是必须选的，没有不选的权利。此时，如果无伤继承dp[i][j]，逻辑就会出问题。

那么咋整呢？既然不让继承，那我不继承不就完了，全靠凑就行了！

这时候，就要体现分组背包的精髓了：每次递推都会有多种情况需要处理，就比如这一题，骰子的点数有6个，这样就注定了我们需要另外开一个循环来遍历骰子的点数。

思路差不多讲完了，还有一些注意事项我放在注释里面了，看代码：

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

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<vector<int>> dp(n+1,vector<int>(target+1,0));
        dp[0][0]=1;
        for (int i=0;i<n;i++) { //枚举骰子
            for (int num=1;num<=k;num++) { //遍历从1到6的骰子
                for (int j=0;j<=target;j++) { //枚举每个可能被凑到的总和
                    //这里不直接累加是因为题目要求取余，数据比较大
                    if (j-num>=0) dp[i+1][j] = (dp[i][j-num]+dp[i+1][j])%MOD; 
                }
            }
        }
        return dp[n][target];
    }
};

接着，我们来看第二题：1981. 最小化目标值与所选元素的差，先看题。

首先，依旧三步走：确定背包容量，确定物品是啥，确定单元格的数据类型以及初始值。

首先，背包容量，这题就很有意思了。一开始我是想着现场计算，把可能的最大和和可能的最小和都算一下，然后再综合参考它们和target的距离，算出来一个乱七八糟结果还错的值。一看题解，我好像忽视了什么很重要的东西，并且我不是第一次掉进这玩意的坑里面了：评测数据的范围。

可以看到，1 <= m, n <= 70并且1 <= mat[i][j] <= 70，说明矩阵最多70行，每行最大值70，因此，就算我们每一行都取最大值，总和不会超过70*70=4900，这是一个完全可以接受的、比较小的数。所以，我们直接将这个作为背包容量就行了。

再确定物品是啥。题目说，每一行选一个数，类比上一题，就相当于是每个骰子投一个数，所以物品就是每一行的任意一个元素，大小就是矩阵mat的行数。

最后确定单元格的数据类型。由于我们要计算和target的最小绝对值之差，我们就需要知道我们能凑成哪些数字。因此，从这个"能"字也能体现出，我们要选择bool类型。

再看看初始值吧。我倾向于定义1base的dp数组，这样可以免去边界情况的处理，就像这样：

int m = mat.size(),n = mat[0].size();
//先找出合适的背包空间
int capacity = 70*70;
vector<vector<bool>> dp(m+1,vector<bool>(capacity+1,false));

很显然，我们没法确定到底能不能凑到这个数，所以我们就采用"能凑到就改成true，凑不到就不管"的方式，初始化为false。

那么我们该如何初始化dp[0][0]呢？先翻译一下它的意思：一个数都不取，能凑成0吗？

当然可以了。而且，这是我们后续所有递推的基础。就算你没理解上面的话，你想想也知道，如果全是false，咱们递推是完全依赖上一步的状态的，那是不可能凭空变出一个true出来的。

dp数组落实完了，我们就可以开始考虑如何递推了。和上一题的投骰子类似，在这一题，我们每一行都必须选一个数，所以我们依旧不考虑无伤继承上一个状态的情况，全部基于上一步凑数的情况看看我这一步选择一个数能不能凑成我想求证的数：如果上一步能凑到j-x，那么我这一步选一个x就肯定能凑成j。这句话就是我们递推的基础。

最后，在dp完之后，dp数组的最后一排就清楚的呈现出，在每一行都选过之后，哪些数能凑成而哪些数不行。我们遍历一下最后一排，把那些凑成功的数和target作差后取绝对值，再维护一个最小值，就能得出答案。

思路讲完了，还是比较顺的，上代码，记得看一眼注释：

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

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(),n = mat[0].size();
        //1.先找出合适的背包空间
        int capacity = 70*70;
        //2.开始dp
        vector<vector<bool>> dp(m+1,vector<bool>(capacity+1,false));
        dp[0][0]=true;
        for (int i=0;i<m;i++) { //遍历行
            for (int j=1;j<=capacity;j++) { //枚举想要求证能否凑到的数
                for (int k=0;k<n;k++) { //从这一行中选择一个数来凑
                    int x = mat[i][k];
                    if (j-x>=0 && dp[i][j-x]) {
                        dp[i+1][j] = true;
                        //这里的剪枝是优化性能的：因为我们只需要求证这个数能不能被凑到
                        //如果能，就够了，再尝试其它凑成这个数的组合除了浪费时间没有任何意义
                        break;
                    }
                }
            }
        }
        //3.找出最小的区别
        int minAns = INT_MAX;
        for (int i=0;i<=capacity;i++) {
            if (dp[m][i]) minAns = min(minAns,abs(i-target));
        }
        return minAns;
    }
};

ok，最后，我们来看第三题：2218. 从栈中取出 K 个硬币的最大面值和，先看题，这题的花样就比较多了。

初看题目：我去，怎么是栈？confused，我打开了题目的算法标签：没有栈？

取而代之的是前缀和，ok，秒懂：由于栈里面的元素只能一个一个取，这样的话，我用前缀和把里面的元素预先处理好，不就能通过我取的数的个数超级快的得出总和了吗？否则，我每个不同的状态的取值情况都不一样，dp可没法携带栈把状态往下传。

解决了这个最基本的问题之后，这道题目就转化成了：有若干个栈，并且限定了总取硬币次数，我需要分配我在各个栈分别取几次硬币，来使得我的硬币总和最大。

这样子，就很好确定本题的"三步走"元素了：

1. 物品的种类和数量。很明显，一个栈对应取不同次数的多个选择，所以栈的数量是物品的种类数量n，一个栈就是一个物品。

2. 背包容量。由于我们需要在k次内完成操作，所以，我们的转移就需要考虑"上一轮操作了几次，我这一轮操作了之后一共操作了几次"，来保证我们能够不超出操作次数。这样，将背包容量定为k+1刚刚好，因为总操作可以是0次到k次。

   顺带一提为啥可以是0次，即使题目保证数是正数：因为如果前面的数都偏小，后面的数都偏大甚至大很多，并且操作次数比较少，那么就可能出现"前面不拿，全拿后面"的情况。允许操作次数为0才会有这种情况发生。

3. 单元格的数据类型以及初始值。由于我们要求最大面值和，显而易见，我们需要在单元格维护当前取的硬币的值的总和。看一眼题目数据范围，嗯，int够用，那就初始化为int类型。然后呢，由于数全都是大于等于1的，这里的初始值取0或者-INT_MAX都是可以的。

接着，我们来确定一下递推逻辑。都把题目模型转化到这种程度了，这一题在转移上和前面两题就没啥差别了。开个三层循环：

1. 第一层循环遍历栈，记为i。
2. 第二层循环遍历我想要计算的当前总操作次数，范围从0到k，记为j。
3. 第三层遍历每个栈可能的数字拿取个数，记为k。这里要注意一点，由于每个栈的长度都不一样，所以范围需要使用.size()方法动态限定。然后还要注意一点，就是拿取的个数除了不能超出栈的长度，还得保证不超过j。
4. 然后递推逻辑是这样的：遍历这一步所有可能的拿取次数，每一个次数都试试，取到当前这一步总和最大的情况。有一点这里和上面两题不太一样，这里是允许"无伤继承"的，只不过没有单独写出来，体现在k可以取0上。

好了，思考到这里，题目差不多就做出来了。剩下的是细节处理，有一些要注意的点我会注释在旁边：

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

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        //1.获取参数
        int n = piles.size();
        //2.给栈中硬币构建前缀和并塞进新数组
        vector<vector<int>> prefixPiles;
        for (int i=0;i<n;i++) {
            auto& curArr = piles[i];
            vector<int> newArr(curArr.size()+1);
            for (int j=0;j<curArr.size();j++) {
                newArr[j+1]=newArr[j]+curArr[j];
            }
            prefixPiles.emplace_back(newArr);
        }
        //3.准备开始dp
        vector<vector<int>> dp(n+1,vector<int>(k+1,-INT_MAX));
        dp[0][0]=0;
        for (int i=0;i<n;i++) {
            //这里由于我前缀和数组是1base，就导致索引0的位置天然的值为0，就能优雅处理k=0时一个都不拿的情况
            int curPileSize = prefixPiles[i].size();
            for (int j=0;j<=k;j++) {
                for (int c=0;c<curPileSize && c<=j;c++) {
                    dp[i+1][j] = max(dp[i+1][j],dp[i][j-c]+prefixPiles[i][c]);
                }
            }
        }
        return dp[n][k];
    }
};

好的，讲解完毕！下一次，我们最长公共子序列（LCS）见！