动态规划

在前驱位置不明确，需要自己查找时，该类型时间复杂度通常为O(),因为在遍历一遍dp时，还需要遍历寻找前驱最优j 在寻找前驱最优dp[j] 时，可以按照 j = range(0, i) 遍历，也可以按照j = range(i-1, -1, -1) 来遍历，只是寻找前驱最优的方式不同，应当根据题意按照最优方式查找

💡

不要被上图误解，每一轮的状态可能不止一个状态，也可能是多个状态，类似基本类型Ⅰ中每一天均有多个状态。上图只是在寻找最佳前驱天（轮）。找到之后，还需要将第j 天的状态和第i天的状态联系起来。所以总结一下就是： 1.先寻找最佳前驱天（轮）j ，（也可能题目告知了最佳前驱，例如983） 2. 寻找第j天的状态和第i天的状态之间的关系本类型之所以称为时间序列增强版，就是因为在基础版的基础上多了第一步：需要先寻找最佳前驱天数。

💡

在解决此类型题目时，先思考如何用一个状态来表达，当一个状态无法表达时，将dp扩展为二维数组，使用多个状态来表达。

💡

每次都要寻找一个前驱 j，需要关注的是，当前找的前驱和之前找的前驱是否有关系，例如 45. 跳跃游戏 II (notion.so) 后面的前驱一定是大于前面的前驱的，所以每次只需要从前面的前驱开始从前往后找即可，找到之后，再更新前驱。

经典题型

🚢

32. 最长有效括号 遇到右括号，就找一个左括号匹配

873. 最长的斐波那契子序列的长度 动态规划和三数之和结合

🎈

1218. 最长定差子序列 动态规划 + hashmap

300. 最长递增子序列 动态规划 + 二分法 → nlogn 的时间复杂度

354. 俄罗斯套娃信封问题

🏈

376. 摆动序列 978. 最长湍流子数组套娃题

爬楼梯变形题，一般是问有多少种方法上楼梯。取决于上一个台阶和上上一个台阶，或者之前的某个台阶。

newcode 左边必有1的二进制字符串的数量

📣

6109. 知道秘密的人数

💡

45，673 91 140 1218 32 873 32

Ⅲ. 双序列型

类型描述

给出两个序列s和t（数组/字符串），让你对它们搞事情。没有太多的花样，套路比较强

最长公共子序列

交错序列

编辑距离

套路

定义dp[i][j]：表示针对s[0:i]（s的前i个字符）和t[0:j]（t的前j个字符）的子问题的求解。

千方百计将dp[i][j]往之前的状态去转移：dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

dp[i-1][j] s序列不取第i个字符

dp[i][j-1] t序列不取第j个字符

dp[i-1][j-1] s序列和t序列均少取最后一个字符

边界条件，列举出来再根据题目意思填充

最终的结果是dp[m][n]

技巧总结

💡

对于字符串题目，可以在字符串前面添加一个空字符“#”，这样在状态转移时索引字符就不用i-1,j-1.尤其是对于由三个字符串要操作的。比如交错序列题目

💡

双序列类型题目一般题干会直接给出两个字符串，但是亦有如下特例对于回文串相关题目，一般题干只会给出一个字符串，这个时候需要会变通，自己再构造一个与所给字符串逆序的字符串。有些题目会给出三个字符串进行可行性分析，比如交错序列，这时肯定有一个字符串是不直接参与状态转移的。

💡

双序列类型题目根据给定序列大体分为两种一种是给定的双序列没有主次之分，例如最长公共子序列，编辑距离。这类题目最大特点就是所给的两个序列可以交换，所以具有较强的对称性，因此在状态转移的时候会用到dp[i-1][j], dp[i][j-1] ,dp[i-1][j-1]这三个子问题另外一种是双序列有主次之分，称为匹配问题，例如正则表达式匹配，最小窗口子序列，不同的子序列。这类题目两个序列一定不能交换。在状态转移的时候往往不会同时用到dp[i-1][j],dp[i][j-1]这两个子问题。

💡

个人习惯：一般将第一个序列放在dp表格列左边，第二个序列放在表格行上面。然后先手推算一遍状态转移方程。

💡

字符串题目，草稿纸上写出 s: xxxxi t: xxj 然后观察s[i] == t[j] 的情况与≠ 的情况

💡

要会根据计算出来的 dp 数组还原结果，比如

经典题型

718. 最长重复子数组动态规划 + 字符串匹配算法

🚃

1092. 最短公共超序列 需要回溯路径

712. 两个字符串的最小ASCII删除和

727. 最小窗口子序列 滑动窗口更好

🕢

1143. 最长公共子序列

🚙

1713. 得到子序列的最少操作次数 最长公共子序列到最长递增子序列的转化

🥉

1035. 不相交的线最长公共子序列模板题

1312. 让字符串成为回文串的最少插入次数

💡

1092需要回溯找路径 97 115 组合问题 44 最长公共子串套娃题：1143，583 ，1216，1312，516，1035，1713

Ⅳ. 第一类区间型DP

类型描述

给出一个序列，明确要求分割成K个连续区间，要你计算这些区间的某个最优性质。

套路

状态定义：dp[i][k]表示针对s[1:i+1]分成k个区间，此时能够得到的最优解，k in [1, K]

突破口在于搜寻最后一个区间的起始位置j，将dp[i][k]分割成dp[j-1][k-1]和s[j:i]两部分。

最终的结果是dp[N][K]

经典题型

Ⅴ. 第二类区间型DP

只给出一个序列S（数组或者字符串），求一个针对该序列的最优解。

特点：最优解对于序列的的index而言，没有“无后效性”。即无法设计dp[i]使得dp[i]仅仅依赖dp[j](j<i)

大区间的最优解依赖于小区间的最优解。想清楚当前选择和子问题之间的关系。

此类题目相当于在填充矩形的右上角

套路

定义dp[i][j]:表示针对s[i:j]的子问题的求解

千方百计的将大区间的dp[i][j]往小区间上面转移

最终的结果是dp[0][-1]

经典题目包括矩阵链乘法及钢条分割，对应leetcode上戳气球和

经典题型

🪀
312. 戳气球 等同矩阵连乘最小相乘次数问题

Ⅵ. 背包问题

有一堆东西，每样东西都有拿或者不拿两种选择，最终得到满足某个条件的结果，这个结果可能是最大价值，可能是能否达到某个具体的值，可能是组合的种类，可能是满足条件的最少物品。

根据每样物品的数量分为：

01背包，每样物品只有一个

完全背包：每样物品无限制

多重背包：每样物品都有不同的数量限制

💡

遍历物品i 遍历背包的容量 j

做选择：选择当前物品 i or 不选择当前物品

在背包问题里求排列的方法是：

排列：先遍历背包容量，再遍历物品例如
🗄️
377. 组合总和 Ⅳ 有点类似爬楼梯：达到目的的方法有很多种。。。

组合：先遍历物品，再遍历背包容量

0-1 背包：每种物品只有一个

给定一个可装载容量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为w[i], 价值为val[i], 现在让你用这个背包装物品，最多能装的价值为多少？

状态定义 dp[i][j]：对于前i个物品，当前背包的容量为j，这种情况下可以装的最大价值为dp[i][j]

状态转移：

第i个物品装入背包，空间减少价值增加。dp[i][j] = dp[i-1][j-w[i]] + val[i]

第i个物品不装如背包，维持不变.。dp[i][j] = dp[i-1][j]

模板：


# N个物品，总容量为 W
# 物品重量 和价值分别为 weight, value
dp = [[0]*(W+1) for _ in range(N+1)]

# 遍历状态
# 状态 i
for i in range(1, N+1):
		# 遍历状态 j
		for j in range(1, W+1):
				# 做选择：选择当前物品 or 不选择当前物品
				dp[i][j] = max(dp[i-1][j],                              # 不把物品i放到背包
												dp[i-1][j-weight[i-1]] + value[i-1]     # 把物品i放到背包

return dp[N][W]

经典题目

💡

注意组合数目的题目，和普通最大价值的题目不一样 494， 879

完全背包物品数量无限

情景和0-1背包类似，只不过完全背包中，每个物品的数量是不限制的。

注意：由于每个物品是不限制数量的，所以在计算满足某某条件的最少物品数目时，如果考虑当前物品，那么应该在当前层上加 1 ，而不是上一层。

模板：


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[i][j] 表示 coin[0:i] 个硬币中组成金额为 j 的最少数目 
        dp = [[float("inf")] * (amount+1) for _ in range(len(coins)+1)]
        # 初始化
        for i in range(0, len(dp)):
            dp[i][0] = 0

        for i in range(1, len(dp)):
            for j in range(1, amount+1):
                # 不考虑当前 硬币
                dp[i][j] = dp[i-1][j]
                # 考虑当前硬币，由于硬币数目是无限制的，所以在当前层上 + 1
                if j - coins[i-1] >= 0:
                    dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]] + 1)

        return dp[-1][amount] if dp[-1][amount] != float('inf') else -1

279. 完全平方数 BFS 更优秀！

377. 组合总和 Ⅳ 70. 爬楼梯的进阶版

691 1449

多重背包每种物品数量有限制

多重背包是可以转化为01背包的。在选择当前物品时，需要遍历选择的数目

🎮

798 · 背包问题VII - LintCode

Ⅶ. 博弈论-公平组合游戏

简介

组合游戏是指一种两个人玩的游戏，每个玩家都有着完全的信息，不存在随机动作，游戏的结果总是赢或者输。游戏的每一步都由一个移动构成，通常玩家会交替的移动，直达达到终点状态。终止状态是指从该状态不存在任何一个状态移动方式的状态。

显然，游戏的结果从一开始就已经被决定的，结果由游戏的状态集合、游戏的初始状态以及玩家的先后手完全决定。

组合游戏的形式有两种，这里我们主要讨论其中的一种游戏形式 Impartial Combinatorial Games，以下简称 ICG。ICG 是指在游戏中，两个玩家所能进行的移动是完全相同的。对应的另一种形式 Partizan Combinatorial Games 就是指两个玩家分别有不同的移动，比如说我们熟知的象棋。

总结

用dp或者dfs 记忆化搜索都可以解答，参考古城算法 or 花花酱。

时间复杂度一般是O(n)，因为每次的选择是有限的。常见的有，从一头开始拿，从两头拿，从一头按照各种规则拿。

这类题目一般比较好分辨，一般为2人游戏，每次的操作都需要 最小化对手下一步的最大收益

涉及分数的，一般都是记录的分数差，即先手比后手多得的分数

经典题目

Ⅷ. 杨辉三角组合数目

用动态规划来计算组合数。

组合相关公式：

可以用动态规划来计算

模板


memo = [[None]*(n+1) for _ in range(n+1)]
# n choice k
def nCk(n,k):
	if n == k or k == 0:
			return 1
	if memo[n][k] is None:
		memo[n][k] = self.nCk(n-1, k-1) + self.nCk(n-1, k)
	return memo[n][k]

经典题目

1916. 统计为蚁群构筑房间的不同顺序

🎹

1569. 将子数组重新排序得到同一个二叉查找树的方案数

1467. 两个盒子中球的颜色数相同的概率

1643. 第 K 条最小指令