前言

从 递归 到 记忆化搜索
从 记忆化搜索 到 动态规划
由顶至底，由底至顶。
无论怎么说，都是对所有状态的穷举。
而如何找出，定义这些状态，是我们所要做的，
这就是 动态规划。

一维DP

前置知识:

需要熟悉递归
关于取模，需要熟悉 同余原理

动态规划：用空间代替重复计算

知道怎么算的算法 vs 知道怎么试的算法

有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益
如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要

任何动态规划问题都一定对应着一个有重复调用行为的递归
所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法

尝试策略 就是 转移方程，完全一回事！
推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻！

当熟悉了从递归到动态规划的转化过程
那么就可以纯粹用动态规划的视角来分析问题了
题目5到题目8，都是纯粹用动态规划的视角来分析、优化的

如果不熟悉这个过程，直接一上来就硬去理解状态转移方程
那么往往会步履维艰、邯郸学步、东施效颦

很多极为优异的想法、设计和优化 来自 努力 or 天赋

建议脚踏实地，真正做好从递归到动态规划的练习

例题分析：

题目1

斐波那契数
测试链接 : https://leetcode.cn/problems/fibonacci-number/

1
2
3
4
5
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
也就是：F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n)

注意：
斐波那契数问题最经典，常见方法时间复杂度O(n)
但是最优解来自矩阵快速幂，时间复杂度可以做到O(log n)

辅助理解：从 朴素递归 到 记忆化搜索 再到 动态规划 再到 动态规划的优化 - 滚动数组。

题目2

最低票价
测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/

1
2
3
4
5
6
7
8
9
10
11
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
每一项是一个从 1 到 365 的整数
火车票有 三种不同的销售方式
一张 为期1天 的通行证售价为 costs[0] 美元
一张 为期7天 的通行证售价为 costs[1] 美元
一张 为期30天 的通行证售价为 costs[2] 美元
通行证允许数天无限制的旅行
例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
那么我们可以连着旅行 7 天(第2~8天)
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费

题目3

解码方法
测试链接 : https://leetcode.cn/problems/decode-ways/

1
2
3
4
5
6
7
8
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"、'B' -> "2" ...'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
例如，"11106" 可以映射为："AAJF"、"KJF"
注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
这是由于 "6" 和 "06" 在映射中并不等价
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
题目数据保证答案肯定是一个 32位 的整数

题目4

解码方法 II
测试链接 : https://leetcode.cn/problems/decode-ways-ii/

1
2
3
4
5
6
7
8
9
10
11
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
'A' -> "1"、'B' -> "2" ...'Z' -> "26"
要 解码 一条已编码的消息，所有的数字都必须分组
然后按原来的编码方案反向映射回字母，可能存在多种方式。例如"11106" 可以映射为："AAJF"、"KJF"
注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
由于答案数目可能非常大，返回10^9 + 7的模

前置题目：91. 解码方法

题目5

丑数 II
测试链接 : https://leetcode.cn/problems/ugly-number-ii/

1
2
3
4
5
6
7
丑数 就是只包含质因数 2、3 或 5 的正整数
默认第1个丑数是1，前几项丑数为:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20,
24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60,
64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125..
给你一个整数n ，请你找出并返回第n个丑数
比如，n = 37，返回125

利用了三指针动态规划解题。
三指针法不是严格意义上的线性筛，但具有类似的线性时间特性。
它是一种动态规划（DP）策略，而非筛法（Sieve）。

题目6

最长有效括号
测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/

1
2
给你一个只包含 '(' 和 ')' 的字符串
找出最长有效（格式正确且连续）括号子串的长度。

DP方法和栈方法。
栈方法的思想是用栈保留 失配位置。

题目7

环绕字符串中唯一的子字符串
测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

1
2
3
4
定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
所以 base 看起来是这样的：
"..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
给你一个字符串 s ，请你统计并返回 s 中有多少 不同、非空子串 也在 base 中出现

题目8

不同的子序列 II
测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/

1
2
3
4
5
给定一个字符串 s，计算 s 的 不同非空子序列 的个数
因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
字符串的 子序列 是经由原字符串删除一些（也可能不删除）
字符但不改变剩余字符相对位置的一个新字符串
例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是

前置题目：115. 不同的子序列

总结：

动态规划的大致过程：
想出设计优良的递归尝试(方法、经验、固定套路很多)，有关尝试展开顺序的说明

  1. 记忆化搜索(从顶到底的动态规划) ，如果每个状态的计算枚举代价很低，往往到这里就可以了
  2. 严格位置依赖的动态规划(从底到顶的动态规划) ，更多是为了下面说的 进一步优化枚举做的准备
  3. 进一步优化空间（空间压缩），一维、二维、多维动态规划都存在这种优化
  4. 进一步优化枚举也就是优化时间

解决一个问题，可能有很多尝试方法
众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划
若干个可以转化成动态规划的方法中，又可能有优劣之分
判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量
最优的动态规划方法实现后，后续又有一整套的优化技巧

二维DP

前置知识:

  1. 递归
  2. 从递归入手一维动态规划

从递归入手二维动态规划

尝试函数有1个可变参数可以完全决定返回值，进而可以改出1维动态规划表的实现
同理
尝试函数有2个可变参数可以完全决定返回值，那么就可以改出2维动态规划的实现
一维、二维、三维甚至多维动态规划问题，大体过程都是：

  1. 写出尝试递归
  2. 记忆化搜索(从顶到底的动态规划)
  3. 严格位置依赖的动态规划(从底到顶的动态规划)
  4. 空间、时间的更多优化

动态规划表的大小：每个可变参数的可能性数量相乘
动态规划方法的时间复杂度：动态规划表的大小 * 每个格子的枚举代价

二维动态规划依然需要去整理 动态规划表的格子之间的依赖关系
找寻依赖关系，往往 通过画图来建立空间感，使其更显而易见
然后依然是 从简单格子填写到复杂格子 的过程，即严格位置依赖的动态规划(从底到顶)

二维动态规划的压缩空间技巧原理不难，会了之后千篇一律
但是不同题目依赖关系不一样，需要 很细心的画图来整理具体题目的依赖关系
最后进行空间压缩的实现

什么递归能改成动态规划？

能改成动态规划的递归，统一特征：
决定返回值的可变参数类型往往都比较简单，一般不会比int类型更复杂。为什么？

从这个角度，可以解释 带路径的递归（可变参数类型复杂），不适合或者说没有必要改成动态规划
题目2就是说明这一点的

一定要 写出可变参数类型简单（不比int类型更复杂），并且 可以完全决定返回值的递归，
保证做到 这些可变参数可以完全代表之前决策过程对后续过程的影响！再去改动态规划！

不管几维动态规划
经常从递归的定义出发，避免后续进行很多边界讨论
这需要一定的经验来预知

例题分析：

题目1

最小路径和
测试链接 : https://leetcode.cn/problems/minimum-path-sum/

1
2
3
给定一个包含非负整数的 m x n 网格 grid
请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

题目2

单词搜索（无法改成动态规划）
测试链接 : https://leetcode.cn/problems/word-search/

1
2
3
4
5
给定一个 m x n 二维字符网格 board 和一个字符串单词 word
如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成
其中"相邻"单元格是那些水平相邻或垂直相邻的单元格
同一个单元格内的字母不允许被重复使用

上位题目：212. 单词搜索 II <- 利用 DFS + 前缀树剪枝 解题

题目3

最长公共子序列
测试链接 : https://leetcode.cn/problems/longest-common-subsequence/

1
2
3
4
给定两个字符串text1和text2
返回这两个字符串的最长 公共子序列 的长度
如果不存在公共子序列，返回0
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列

题目4

最长回文子序列
测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/

1
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
  1. 用原始串和逆序串转化为 LCS问题 即 题目3
  2. 区间DP思路

题目5

节点数为n高度不大于m的二叉树个数
测试链接 : https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea

1
2
3
现在有n个节点，计算出有多少个不同结构的二叉树
满足节点个数为n且树的高度不超过m的方案
因为答案很大，所以答案需要模上1000000007后输出

题目6

矩阵中的最长递增路径
测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

1
2
3
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度
对于每个单元格，你可以往上，下，左，右四个方向移动
不能在对角线方向上移动或移动到边界外（即不允许环绕）

做到记忆化搜索就行，依赖关系混乱还不如不DP

二维DP - 拓展 - 直接从动态规划的定义入手

前置知识：

  • 二维DP - 从递归入手二维动态规划

例题分析：

题目1

不同的子序列
测试链接 : https://leetcode.cn/problems/distinct-subsequences/

1
2
3
给你两个字符串s和t
统计在s的所有子序列中
有多少个子序列等于t

题目2

编辑距离
测试链接 : https://leetcode.cn/problems/edit-distance/

1
2
3
4
5
6
给你两个单词 word1 和 word2
请返回将 word1 转换成 word2 所使用的最少代价
你可以对一个单词进行如下三种操作：
插入一个字符，代价a
删除一个字符，代价b
替换一个字符，代价c

实际上就是 LCS问题

题目3

交错字符串
测试链接 : https://leetcode.cn/problems/interleaving-string/

1
2
给定三个字符串 s1、s2、s3
请帮忙验证s3是否由s1和s2交错组成

看起来像三维，实际上第三个参数是由第一和第二个决定的。

题目4

有效涂色问题

1
2
3
4
5
6
7
给定n、m两个参数
一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
求一共有多少种有效的涂色方法
1 <= n, m <= 5000
结果比较大请 % 1000000007 之后返回
对数器验证

题目5

删除至少几个字符可以变成另一个字符串的子串

1
2
3
给定两个字符串s1和s2
返回s1至少删除多少字符可以成为s2的子串
对数器验证

三维DP

前置知识：

  • 从递归入手二维动态规划

从递归入手三维动态规划

尝试函数有1个可变参数可以完全决定返回值，进而可以改出1维动态规划表的实现
同理
尝试函数有2个可变参数可以完全决定返回值，那么就可以改出2维动态规划的实现
同理
尝试函数有3个可变参数可以完全决定返回值，那么就可以改出3维动态规划的实现

大体过程都是：

  1. 写出尝试递归
  2. 记忆化搜索(从顶到底的动态规划)
  3. 严格位置依赖的动态规划(从底到顶的动态规划)
  4. 空间、时间的更多优化

例题分析：

题目1

一和零(多维费用背包)
测试链接 : https://leetcode.cn/problems/ones-and-zeroes/

1
2
3
4
给你一个二进制字符串数组 strs 和两个整数 m 和 n
请你找出并返回 strs 的最大子集的长度
该子集中 最多 有 m 个 0 和 n 个 1
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集

题目2

盈利计划(多维费用背包)
测试链接 : https://leetcode.cn/problems/profitable-schemes/

1
2
3
4
5
6
集团里有 n 名员工，他们可以完成各种各样的工作创造利润
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与
如果成员参与了其中一项工作，就不能参与另一项工作
工作的任何至少产生 minProfit 利润的子集称为 盈利计划
并且工作的成员总数最多为 n
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

题目3

骑士在棋盘上的概率
测试链接 : https://leetcode.cn/problems/knight-probability-in-chessboard/

1
2
3
4
5
6
n * n的国际象棋棋盘上，一个骑士从单元格(row, col)开始，并尝试进行 k 次移动
行和列从0开始，所以左上单元格是 (0,0)，右下单元格是 (n-1, n-1)
象棋骑士有8种可能的走法。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格
每次骑士要移动时，它都会随机从8种可能的移动中选择一种，然后移动到那里
骑士继续移动，直到它走了 k 步或离开了棋盘
返回 骑士在棋盘停止移动后仍留在棋盘上的概率

题目4

矩阵中和能被 K 整除的路径
测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

1
2
3
4
给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
请你返回路径和能被 k 整除的路径数目
由于答案可能很大，返回答案对10^9+7取余的结果

题目5

扰乱字符串
测试链接 : https://leetcode.cn/problems/scramble-string/

1
2
3
4
5
6
7
8
9
10
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
步骤1 : 如果字符串的长度为 1 ，算法停止
步骤2 : 如果字符串的长度 > 1 ，执行下述步骤：
       在一个随机下标处将字符串分割成两个非空的子字符串
       已知字符串s，则可以将其分成两个子字符串x和y且满足s=x+y
       可以决定是要 交换两个子字符串 还是要 保持这两个子字符串的顺序不变
       即s可能是 s = x + y 或者 s = y + x
       在x和y这两个子字符串上继续从步骤1开始递归执行此算法
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串
如果是，返回true ；否则，返回false

子数组最大累加和 - Kadane’s算法

前置知识:

  1. 二分答案法
  2. 从递归入手一维动态规划

子数组最大累加和问题是一个非常经典的问题，也比较简单
为什么叫 Kadane’s算法 ？
Kadane 当时是美国卡内基梅隆大学（Carnegie Mellon University）的统计学家。他在一次内部讨论中，提出了解决最大子数组和问题的线性时间算法，这个问题最初是为了解决股票收益最大化场景（即找出某段时间内的最佳买卖时机）。

这套算法后来被广泛传播并引用，逐渐被称为：

Kadane’s Algorithm
（Kadane 的算法）

例题分析：

题目1
测试链接 : https://leetcode.cn/problems/maximum-subarray/

1
2
3
4
5
6
7
8
9
10
11
子数组最大累加和
给你一个整数数组 nums
请你找出一个具有最大累加和的非空子数组
返回其最大累加和

附加问题
子数组中找到拥有最大累加和的子数组，并返回如下三个信息:
1) 最大累加和子数组的开头left
2) 最大累加和子数组的结尾right
3) 最大累加和子数组的累加和sum
如果不止一个子数组拥有最大累加和，那么找到哪一个都可以

题目2

不能选相邻元素的最大累加和问题
测试链接 : https://leetcode.cn/problems/house-robber/

1
2
给定一个数组，可以随意选择数字，但是不能选择相邻的数字
返回能得到的最大累加和

题目3

环形数组的子数组最大累加和
测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/

1
2
3
给定一个数组nums，长度为n
nums是一个环形数组，下标0和下标n-1是连在一起的
返回环形数组中子数组最大累加和

两种情况

  1. 最大累加和子数组没有被分割：转化为 问题一
  2. 最大累加和子数组被分割：实际上就是 子数组总和 - 子数组最小累加和
    另外 要警惕 子数组最小累加和 == 子数组总和 的特例

题目4

环形数组中不能选相邻元素的最大累加和
测试链接 : https://leetcode.cn/problems/house-robber-ii/

1
2
3
4
给定一个数组nums，长度为n
nums是一个环形数组，下标0和下标n-1是连在一起的
可以随意选择数字，但是不能选择相邻的数字
返回能得到的最大累加和

两种情况

  1. 要 0 位置上的数，问题转化为：在(1, size - 1)范围上求 问题2
  2. 要 size - 1 位置上的数，问题转化为：在(0, size - 2)范围上求 问题2

题目5

打家劫舍 IV
测试链接 : https://leetcode.cn/problems/house-robber-iv/

1
2
3
4
5
6
7
8
沿街有一排连续的房屋。每间房屋内都藏有一定的现金
现在有一位小偷计划从这些房屋中窃取现金
由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
给你一个整数数组 nums 表示每间房屋存放的现金金额
第i间房屋中放有nums[i]的钱数
另给你一个整数k，表示小偷需要窃取至少 k 间房屋
返回小偷需要的最小窃取能力值

二分答案 + 问题2
check函数的设计就是 问题2
因为题目只要求能偷的房间数，
所以在此基础上还可以继续贪心优化减小常数时间，
贪心思路：能偷就偷，不能偷就移动到下一个能偷的点。

题目6

子矩阵最大累加和问题
测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/

1
2
3
给定一个二维数组grid，找到其中子矩阵的最大累加和
返回拥有最大累加和的子矩阵左上角和右下角坐标
如果有多个子矩阵都有最大累加和，返回哪一个都可以

压缩数组转化为 问题1

子数组最大累加和(下)

前置知识:

  1. 对数器
  2. 构建前缀信息的技巧
  3. 单调队列，一定要掌握，本节课题目6需要，后续讲“多重背包的单调队列优化”也需要
  4. 子数组最大累加和问题与扩展-上

例题分析：

题目1

乘积最大子数组
测试链接 : https://leetcode.cn/problems/maximum-product-subarray/

1
2
3
4
5
6
7
给你一个double类型数组 nums
请你找出数组中乘积最大的非空连续子数组
并返回该子数组所对应的乘积

注意：
题目中虽然给定的是int类型的数组
但讲述的方法是int、double类型的数组都能正确的做法

与 最大子数组累加和 问题的差异点在于：考虑负负得正情况，
即有可能最优解来自于最小的累乘积与当前负数的积。

题目2

子序列累加和必须被7整除的最大累加和

1
2
3
4
给定一个非负数组nums，
可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
返回最大累加和
对数器验证

dp[i][j]定义：nums 前 i 个数中，形成的子序列累加和 % 7 == j
最终答案返回dp[n][0]

题目3

魔法卷轴

1
2
3
4
5
6
给定一个数组nums，其中可能有正、负、0
每个魔法卷轴可以把nums中连续的一段全变成0
你希望数组整体的累加和尽可能大
卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴
请返回数组尽可能大的累加和
对数器验证

三种情况：

  1. 不用：累加。
  2. 用一次：维护一个 一定用了一次卷轴 的 前缀和数组 即 在0 ~ i范围上 前缀和最好 的 前缀和数组。
  3. 用两次：同上，不过是构建 特殊后缀和数组，然后枚举划分点。

题目4

三个无重叠子数组的最大和
测试链接 : https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/

1
2
3
4
5
给你一个整数数组 nums 和一个整数 k
找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组
并返回这三个子数组
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置
如果有多个结果，返回字典序最小的一个

建立辅助信息：
sums[i]: 以 i 开头 长度为k的 的 区间累计和。
prefix[i]: 在 range(0, i) 上 长度为k的子数组 中 最大sum 的子数组 的 开头在哪。
suffix[i]: 在 range(i, n - 1) 上 长度为k的子数组 中 最大sum 的子数组 的 开头在哪。

三个划分：range1(0, i - 1) <-> range2(i, j) <-> range3(j + 1, n - 1)
range1可以从prefix获取，range3可以从suffix获取，只额外需要枚举range2即可。

题目5

可以翻转1次的情况下子数组最大累加和

1
2
3
4
5
给定一个数组nums，
现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整
比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6]
返回必须随意翻转1次之后，子数组的最大累加和
对数器验证

分析要点：剖析 翻转区间 与 答案区间 的关系。
枚举思路：翻转区间）+（以 i 开头的答案区间
这样我们就可以关注 以 i 开头往右延伸的的最大和区间最大值
和 以 i - 1 开头往左延伸的最大和区间最大值

题目6

删掉1个数字后长度为k的子数组最大累加和

1
2
3
4
5
6
给定一个数组nums，求必须删除一个数字后的新数组中
长度为k的子数组最大累加和，删除哪个数字随意
对数器验证

注意：
确保 单调队列 已经掌握

问题转化为，在原数组中长度为 k + 1 的子数组中最大累加和减去 子数组中最小值。

最长递增子序列

前置知识:

  1. 二分搜索
  2. 一维动态规划

【算法讲解072【必备】最长递增子序列问题与扩展】
补充：该问题也可以线段树求解

例题分析

题目1

最长递增子序列
测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/

1
2
3
4
5
给定一个整数数组nums
找到其中最长严格递增子序列长度、最长不下降子序列长度

最长不下降子序列
只需要改写二分策略即可
  • O(n^2)解
    dp[i]: 以 i 结尾的最长严格递增子序列长度
  • O(nlb(n))解(最优解)
    dp[i]: 以 i 结尾的最长严格递增子序列长度
    ends[i]: 目前所有长度为 i+1 的递增子序列的最小结尾
    实际上就是维护了一个具有单调性的 ends数组 方便二分搜索

题目2

俄罗斯套娃信封问题
测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/

1
2
3
4
5
6
7
给你一个二维整数数组envelopes
其中envelopes[i]=[wi, hi]
表示第 i 个信封的宽度和高度
当另一个信封的宽度和高度都比这个信封大的时候
这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
即可以把一个信封放到另一个信封里面，注意不允许旋转信封

定义一个排序规则,按照宽度从小到大排列且同样宽度的就按照高度从大到小排列
然后排序后单独关注高度求 最大严格递增子序列问题即可
这样就保证了单独关注高度时,某个高度的 信封 左侧的信封宽度一定小于等于当前信封
这样做可以分离宽度对高度的干扰

题目3

使数组K递增的最少操作次数
测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

1
2
3
4
5
给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
如果对于每个满足 k <= i <= n-1 的下标 i
都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
请你返回对于给定的 k ，使数组变成K递增的最少操作次数

实际上就是将 原数组 分为 k 组，这 k组 数据就互不干扰了，
然后对 k组 数据操作将其变为单调递增序列，实际上就是对其求最长不下降子序列长度。

题目4

最长数对链
测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

1
2
3
4
5
6
给你一个由n个数对组成的数对数组pairs
其中 pairs[i] = [lefti, righti] 且 lefti < righti
现在，我们定义一种 跟随 关系，当且仅当 b < c 时
数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
我们用这种形式来构造 数对链
找出并返回能够形成的最长数对链的长度

实际上也是最长递增子序列问题
不过维护 ends数组 的过程中，需要注意，在长度相同的情况下，只维护尽可能小的右部分值。
查询与更新分离的思想

贪心解法：以右部值排序，用一个 pre 变量跟踪前一个右部值，遍历数对，能连接的就连接。

题目5

有一次修改机会的最长不下降子序列
测试链接 : https://www.luogu.com.cn/problem/P8776

1
2
3
4
5
给定一个长度为n的数组arr，和一个整数k
只有一次机会可以将其中连续的k个数全修改成任意一个值
这次机会你可以用也可以不用，请返回最长不下降子序列长度
1 <= k, n <= 10^5
1 <= arr[i] <= 10^6

看视频去
cur
…i)(…k…)(j…
三个range，三个贡献。
同时，查询与更新分离的思想。
有点像前一题，数对。
数对的形式是(l, r)
这一题的形式是(l, range(k), r)

预告

最长递增子序列的数量问题
给定一个未排序的整数数组nums，返回最长递增子序列的个数
测试链接 : https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

这个问题的最优解能做到O(n * logn)
会放在【扩展】课程阶段，详解树状数组(index tree)的时候来讲解
用这个高级数据结构来求解这个题会很方便

这里为什么要提呢？主要是想说：巧妙构思 vs 成熟体系

广阔视野带来的高维思考，这就是启发