• 组合问题

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过

• used[i - 1] == false，说明同一树层candidates[i - 1]使用过（因为前面有一样的元素，但你这一分支没用过，说明别人在用了，你用不了）

关于寻找具体方案？

• 线性DP
• 单串 dp[i] 以nums[i]结尾
• 双串 dp[i][j]
• 背包

• 区间DP

组合优化

NPC问题

• 矩阵：边上一般单独处理一下

• 它们都是将原问题分解为子问题进行求解

• 子问题独立的情况我们使用递归算法解决即可；但如果子问题重叠计算，我们可以使用DP优化

回溯

• 子集型回溯

• 组合型回溯

• TODO：排列型回溯

1. 站在答案的角度看，每个节点的选择都是一个答案

1. 站在输入的角度看，就是当前元素选 / 不选，叶子就是答案

• 组合问题：N个数里面按一定规则找出k个数的集合

• 切割问题：一个字符串按一定规则有几种切割方式

• 子集问题：一个N个数的集合里有多少符合条件的子集

• 排列问题：N个数按一定规则全排列，有几种排列方式

• 棋盘问题：N皇后，解数独等等

动态规划 DP

DP萌新三步

1. 思考回溯怎么写
1. 入参和返回值
2. 递归到哪里（非边界，就是怎么递推）
3. 递归边界和入口

2. 改成记忆化搜索

3. 1:1 翻译成递推：把dfs改成数组f，递归改

1. 确定dp数组以及下标的含义（一般是用来确定子问题）
1. dp xx代表target

2. 确定递推公式（如何依赖子问题的）

3. dp数组如何初始化（用于确保在一开始推导时依赖的数值正确，对于没有的状态，我们要去避免依赖，或者给一个不影响最终答案的初始值）

4. 确定遍历顺序（依赖前面还是依赖后面）

5. 举例推导dp数组（这一步主要用来验证）

回溯三问：

1. 当前操作？ 枚举第 i 个房子选 / 不选

2. 子问题？ 从前 i 个房子中得到的最大金额

3. 当前问题？ 分类讨论：
1. 不选：从前 i - 1 个房子中得到的最大金额
2. 选：从前 i - 2 个房子中得到的最大金额

• 无后效性：已经求解的子问题，不会受到选择的影响

• 最优子结构：原问题的最优解可以由子问题的最优解推导而来

• 边界条件特殊处理、正确初始化

• 避免下标越界

树形DP

树是天然的原问题和子问题结构，我们就考虑选或不选、选哪个，由子问题推出原问题

树的直径

遍历二叉树，计算最长链（返回给父节点使用），同时计算直径(每个节点都可能拐弯，都看一遍）

在当前节点「拐弯」的直径 = 左子树的最长链 + 右子树的最长链 + 1

return给父节点以当前节点为root的最长链 = max（左子树的最长链，右子树的最长链）+ 1

路径上的点数 == 路径上的边数 + 1

一般树：

• 维护列表，先遍历完，然后排序列表并取最值操作

• 直接动态维护最值，在遍历中同时更新

如果邻居包含父节点，就把父节点加入dfs的args，在逻辑内单独判断就行

建图

题目：给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

邻接表（也是用二维表示）：

• 列表（知道节点个数n）

• 哈希表（没必要，一般都知道节点个数n）

最大独立集

节点不相邻

对于节点i如果去考虑儿子的儿子，情况太复杂。直接让每个子节点（i-1）维护两个状态（选/不选），就不用去考虑i-2了

树上最大支配集

 

蓝色 = min（左蓝，左黄，左红） + min（右蓝，右黄，右红） + 1

 

优化：

每个节点都return min（蓝，红），如果真的不幸，选的都是红色节点（蓝-红<0），那就选一个最大的负数

红色 = 黄色 + max（0，min（各个节点的差值））

只要有一个节点选了蓝色（大于红色），就只会加上0

C++用tuple一次返回多个值，可以用[]接收

子序列

子序列就是数组的一个子集，所以我们可以用子集型回溯来解决 选/不选？ 选哪个？

最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/solution/jiao-ni-yi-bu-bu-si-kao-dpfu-o1-kong-jia-4zma/

对于选哪个，我们只需要知道当前数字的下标，更好写

j是需要枚举的

和下一题的联系

把原数组sort后，把两者取一个最长公共子序列，就是最长递增子序列

DP的优化技巧

 

只有定义成最小值，我们才有机会更新长度；维护更小的最小值，可以增大更新长度的可能性

按照这样的定义，并没有子问题，所以不能算DP，反而算是贪心

贪心的证明：

• 反证法

• 数学归纳法

最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/solutions/2133188/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-lbz5/

• 不需要考虑只选一个（只会更差）

• 不需要考虑都不选（已包含，相当于只选一个的子问题）

 

单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

递归搜索 + 记忆化

递推

滚动数组（两个数组）

一个数组

 

因为左上的状态会被之前的计算覆盖掉

所以用一个临时变量pre存起来

 

编辑距离

背包问题

• 01背包

• 完全背包

• 多重背包

背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。

先遍历物品还是先遍历背包重量呢？

要看转移方程，如果是从左上角方向转移而来（包括正上方向），不影响

但一般先遍历物品再遍历背包这个顺序更好理解。

推导公式估计看一遍就记下来了，但难就难在如何初始化和遍历顺序上。

01背包

如果采用暴力穷举的方式，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是

而使用动态规划可以将复杂度降至。我们的目标是书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态：

那么dp[i][j]有两种情况：

1. 不装入第i件（这里不是前i件）物品，即dp[i−1][j]；

2. 装入第i件物品（前提是能装下），即dp[i−1][j−w[i]] + v[i]

即状态转移方程为：

优化

由上述状态转移方程可知，dp[i][j]的值只与dp[i-1][0,...,j-1]有关

所以可以采用滚动数组对空间进行优化（即去掉dp的第一维）

需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举

另一个角度思考：（不如注释，但也是一层很重要的意思）

从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

 

代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

滚不起来，dp[i−1][j−w[i]] i-1统一，但是用j−w[i] 不统一

 

 

动态规划的核心思想

避免重复计算：第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定，暴力枚举忽略了这个事实。

完全背包

每种物品有无限多个

我们的目标和变量和01背包没有区别，所以我们可定义与01背包问题几乎完全相同的状态:

dp[i][j]也有两种情况：

1. 不装入第i种物品，即dp[i−1][j]，同01背包；

2. 装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品

与01背包问题唯一不同就是max第二项不是dp[i-1]而是dp[i]

优化

优化后不同点在于这里的 j 只能正向枚举而01背包只能逆向枚举

多重背包

物品的数量为n[i]

状态定义还是一样：

从装入第 i 种物品多少件出发：装入第i种物品0件、1件、...n[i]件（还要满足不超过限重）

转移方程：

优化

转换成01背包

01背包问题是最基本的背包问题，我们可以考虑把背包问题转化为01背包问题来解：将一种物品转换成若干件只能装入0件或者1件的01背包中的物品。

最简单的想法是，考虑到第 i 种物品最多装入 W/w[i] 件，于是可以把第 i 种物品转化为 W/w[i] 件物品，费用及价值均不变，然后求解这个01背包问题。

更高效的转化方法是采用二进制的思想：

把第 i 种物品拆成重量为 、价值为的若干件物品，其中 k 取遍满足的非负整数。这是因为不管最优策略选几件第 i 种物品，总可以表示成若干个刚才这些物品的和。这样就将转换后的物品数目降成了对数级别。

将第i种物品分成了件物品，将原问题转化为了复杂度为的01背包问题

（例：13 = 1 + 4 + 8）

变种

恰好装满

如果没有恰好装满背包的限制，我们将dp全部初始化成0就可以了。因为任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

如果有恰好装满的限制，那只应该将dp[0,...,N][0]初始为0，其它dp值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。

求方案数

装满背包或将背包装至某一指定容量的方案总数

在状态转移方程中进行统计

二维背包

前面讨论的背包容量都是一个量：重量。二维背包问题是指每个背包有两个限制条件（比如重量和体积限制），选择物品必须要满足这两个条件。

具体方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由哪一个策略推出来的，这样便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。

以01背包为例，我们可以再用一个数组G[i][j]来记录方案，设 G[i][j] = 0表示计算 dp[i][j] 的值时是采用了max中的前一项(也即dp[i−1][j])，G[i][j] = 1 表示采用了方程的后一项。即分别表示了两种策略: 未装入第 i 个物品及装了第 i 个物品。其实我们也可以直接从求好的dp[i][j]反推方案：若 dp[i][j] = dp[i−1][j] 说明未选第i个物品，反之说明选了。