五、股票问题
买卖股票的最佳时机（LeetCode-121）
题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
思路
dp[i][取0或1] 的含义
d p [ i ] [ 0 ] 表示第 i 天持有该股票所得现金
d p [ i ] [ 1 ] 表示第 i 天不持有该股票所得现金
递推公式
d p [ i ] [ 0 ]可由两个状态推出
第 i − 1 天持有股票，则等于 d p [ i − 1 ] [ 0 ]
第 i ii 天买入股票，所得现金就为今天买入后 − p r i c e [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 1 ] 可由两个状态推出
第 i − 1天不持有股票，则等于 d p [ i − 1 ] [ 0 ]
第 i 天卖出股票，则等于 p r i c e [ i ] + d p [ i − 1 ] [ 0 ]
选择所得现金最多的，即二者较大值
数组初始化
dp[0][0] 表示第0天持有股票，所以等于 − p r i c e [ 0 ]
dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
从前往后
测试用例
把用例自己脑子过一遍就懂了
代码展示
class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); vector> dp(n, vector(2)); dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], -prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[n - 1][1]; } };
滚动数组优化！
从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。
因此只要记录前一天和当天的状态就行
class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); vector> dp(2, vector(2)); dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < n; i++) { dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]); dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]); } return dp[(n - 1) % 2][1]; } };
这优化法属实是把二进制玩明白了，我大为震撼。
买卖股票的最佳时机Ⅱ（LeetCode-122）
题目
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
思路
区别就在于可以多次买入！
唯一区别就在于递推公式的 d p [ i ] [ 0 ]
五部曲
dp[i][取0或1] 的含义
d p [ i ] [ 0 ] 表示第 i 天持有该股票所得现金
d p [ i ] [ 1 ] 表示第 i 天不持有该股票所得现金
递推公式
d p [ i ] [ 0 ] 可由两个状态推出
第 i − 1天持有股票，则等于 d p [ i − 1 ] [ 0 ]
第 i 天买入股票，由于可以多次买入，可能会出现之前已经买卖过一轮产生利润的情况，所得现金就为今天买入后 d p [ i − 1 ] [ 1 ] − p r i c e [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 1 ] 可由两个状态推出
第 i − 1 天不持有股票，则等于 d p [ i − 1 ] [ 1 ]
第 i 天卖出股票，则等于 p r i c e [ i ] + d p [ i − 1 ] [ 0 ]
选择所得现金最多的，即二者较大值
数组初始化
dp[0][0] 表示第0天持有股票，所以等于 − p r i c e [ 0 ]
dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
从前往后
代码展示
class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); vector> dp(n, vector(2)); dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[n - 1][1]; } };
买卖股票的最佳时机Ⅲ（LeetCode-123）
题目
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1] 输出：0
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 105
思路
区别在于最多2次交易！
五部曲
dp[i][j] 的含义
一天一共有五种状态
0——没有操作
1——第一次买入
2——第一次卖出
3——第二次买入
4——第二次卖出
d p [ i ] [ j ] 表示在第 i天，状态 j下（j为上五种状态）所剩的最大现金
递推公式
d p [ i ] [ 1 ] 表示第一次买入股票的状态，并不是说一定在当天买入，可以之前买入，该天沿用。可由两个状态推出
第 i 天没有操作，沿用前一天状态，则等于 d p [ i − 1 ] [ 1 ]
第 i 天第一次买入股票，则等于 d p [ i − 1 ] [ 0 ] − p r i c e [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 2 ] 可由两个状态推出
第 i 天没有操作，沿用前一天状态，则等于 d p [ i − 1 ] [ 2 ]
第 i天第一次卖出股票，则等于 d p [ i − 1 ] [ 1 ] + p r i c e s [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 3 ] 可由两个状态推出
d p [ i ] [ 3 ] = m a x ( d p [ i − 1 ] [ 3 ] , d p [ i − 1 ] [ 2 ] − p r i c e s [ i ] )
d p [ i ] [ 4 ] 可由两个状态推出
d p [ i ] [ 4 ] = m a x ( d p [ i − 1 ] [ 4 ] , d p [ i − 1 ] [ 3 ] + p r i c e s [ i ] )
数组初始化
dp[0][0] 等于零
dp[0][1] 等于 − p r i c e [ 0 ]
dp[0][2] 虽然题目没有明确说是否允许同一天内买入并且卖出，但都不影响，因为这一操作收益始终为零
dp[0][3] 等于 − p r i c e [ 0 ]
dp[0][4] 等于零
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); vector> dp(n, vector(5)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]); dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]); dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]); dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]); } return dp[n - 1][4]; } };
这题比较复杂，但理清每个状态的含义就很清晰了
买卖股票的最佳时机Ⅳ（LeetCode-188）
题目
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
思路
在做了买卖股票的最佳时机Ⅲ（LeetCode-123）后，肯定明白了除了状态0，其他的都是奇数买入，偶数卖出
五部曲就不写了，直接参考买卖股票的最佳时机Ⅲ（LeetCode-123）
代码展示
class Solution { public: int maxProfit(int k, vector &prices) { int n = prices.size(); if (n == 0) { return 0; } vector> dp(n, vector(2 * k + 1)); for (int j = 0; j < k; j++) { dp[0][j * 2 + 1] = -prices[0]; } for (int i = 1; i < n; i++) { for (int j = 0; j < k; j++) { dp[i][j * 2 + 1] = max(dp[i - 1][j * 2] - prices[i], dp[i - 1][j * 2 + 1]); dp[i][j * 2 + 2] = max(dp[i - 1][j * 2 + 1] + prices[i], dp[i - 1][j * 2 + 2]); } } return dp[n - 1][k * 2]; } };
最佳买卖股票时机含冻结期（LeetCode-309）
题目
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
思路
五部曲
dp[i][j] 的含义
四种状态
状态一：买入股票状态（今天买入股票或者之前买入就没有操作了）
状态二：两天前就卖出了股票，度过了冷冻期
状态三：今天卖出股票
状态四：今天为冷冻期
递推公式
d p [ i ] [ 0 ] 可由两个状态推出
第 i − 1 天持有股票，则等于 d p [ i − 1 ] [ 0 ]
第 i天买入股票（今天买入），分两种情况
前一天是冷冻期：d p [ i − 1 ] [ 3 ] − p r i c e s [ i ]
前一天是保持卖出股票状态：d p [ i − 1 ] [ 1 ] − p r i c e s [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 1 ] 可由两个状态推出
第 i − 1 天就已经是状态二，则等于 d p [ i − 1 ] [ 1 ]
前一天是冷冻期，则等于 d p [ i − 1 ] [ 3 ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 2 ]只由一个状态推出
前一天一定是买入股票的状态（状态一）：d p [ i − 1 ] [ 0 ] + p r i c e s [ i ]
d p [ i ] [ 3 ] 只由一个状态推出
前一天一定是卖出股票的状态（状态三）：d p [ i − 1 ] [ 2 ]
数组初始化
dp[0][0] 表示第0天买入股票，所以等于 − p r i c e [ 0 ]
遍历顺序
从前往后
代码展示
class Solution { public: int maxProfit(vector &prices) { int n = prices.size(); vector> dp(n, vector(4)); dp[0][0] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])); dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]); dp[i][2] = dp[i - 1][0] + prices[i]; dp[i][3] = dp[i - 1][2]; } return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3])); } };
这题挺绕的，不看题解完全不会写。
买卖股票的最佳时机含手续费（LeetCode-714）
题目
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
提示：
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104
思路
和 LeetCode-122 差不多类型，只要卖出时减去手续费就行
五部曲
dp[i][取0或1] 的含义
d p [ i ] [ 0 ] 表示第 i 天持有该股票所得现金
d p [ i ] [ 1 ] 表示第 i 天不持有该股票所得现金
递推公式
d p [ i ] [ 0 ] 可由两个状态推出
第 i − 1 天持有股票，则等于 d p [ i − 1 ] [ 0 ]
第 i 天买入股票，由于可以多次买入，可能会出现之前已经买卖过一轮产生利润的情况，所得现金就为今天买入后 d p [ i − 1 ] [ 1 ] − p r i c e [ i ]
选择所得现金最多的，即二者较大值
d p [ i ] [ 1 ] 可由两个状态推出
第 i − 1天不持有股票，则等于 d p [ i − 1 ] [ 1 ]
第 i ii 天卖出股票，则等于 p r i c e [ i ] + d p [ i − 1 ] [ 0 ] − f e e
选择所得现金最多的，即二者较大值
数组初始化
dp[0][0] 表示第0天持有股票，所以等于 − p r i c e [ 0 ]
dp[0][1] 表示第0天不持有股票，等于0
遍历顺序
从前往后
代码展示
class Solution { public: int maxProfit(vector &prices, int fee) { int n = prices.size(); vector> dp(n, vector(2)); dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee); } return dp[n - 1][1]; } };
六、子序列问题
一、子序列（连续）
最长上升子序列（LeetCode-300）
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
思路
五部曲
dp[i] 含义
包含下标 i ii 的最长上升子序列
递推公式
寻找从 0 到 i − 1各个位置的最长上升子序列加一的最大值
在 n u m s [ i ] > n u m s [ j ] 的情况下
d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 )
数组初始化
每一个最长上升子序列起始长度至少为1
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int lengthOfLIS(vector &nums) { int n = nums.size(); vector dp(n, 1); int result = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } result = max(dp[i], result); } return result; } };
最长公共子序列（LeetCode-1143）
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
思路
五部曲
dp[i][j] 含义
长度为 [ 0 , i − 1 ] 的字符串text1与长度为 [ 0 , j − 1 ] 的字符串text2的最长公共子序列长度
递推公式
如果 t e x t 1 [ i − 1 ] = t e x t 2 [ j − 1 ]
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1
如果二者不相等
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] )
数组初始化
dp[i][0] 与空串一起求最长公共子序列，自然为零
dp[0][j] 同理等于零
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(); int n2 = text2.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return dp[n1][n2]; } };
不相交的线（LeetCode-1035）
题目
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2] 输出：3
示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1] 输出：2
提示：
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000
思路
本质上和最长公共子序列（LeetCode-1143）一模一样。（公共子序列里的排序顺序不能改变）
代码展示
class Solution { public: int maxUncrossedLines(vector &nums1, vector &nums2) { int n1 = nums1.size(); int n2 = nums2.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return dp[n1][n2]; } };
二、子序列（连续）
最长连续递增序列（LeetCode-674）
题目
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1
提示：
1 <= nums.length <= 104
-109 <= nums[i] <= 109
思路
五部曲
dp[i] 含义
包含下标 i 的最长连续递增序列
递推公式
判断下标 i − 1是否是最长连续递增序列，如果是，加一
在 n u m s [ i ] > n u m s [ i − 1 ] 的情况下
d p [ i ] = d p [ i − 1 ] + 1
数组初始化
每一个最长上升子序列起始长度至少为1
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int findLengthOfLCIS(vector &nums) { int n = nums.size(); vector dp(n, 1); int result = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { dp[i] += dp[i - 1]; } result = max(result, dp[i]); } return result; } };
比单纯的最长子序列还要简单
最长重复子数组（LeetCode-718）
题目
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
思路
和最长公共子序列（LeetCode-1143）的区别在于那题不要求连续，而本题是必须连续的子数组。
代码展示
class Solution { public: int findLength(vector &nums1, vector &nums2) { int n1 = nums1.size(); int n2 = nums2.size(); vector> dp(n1 + 1, vector(n2 + 1)); int result = 0; for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } result = max(result, dp[i][j]); } } return result; } };
最大子序和（LeetCode-53）
题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路
五部曲
dp[i] 含义
包含下标 i ii 的最大连续子数组和
递推公式
前面的最大和加上当前元素的值首先必须是正的才有积极意义，其次如果小于当前元素值，那么当前元素就没有必要带前面的一起，不如自己当头元素
d p [ i ] = m a x ( d p [ i − 1 ] + n u m s [ i ] , n u m s [ i ] )
数组初始化
dp[0] 应该等于 n u m s [ 0 ]
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int maxSubArray(vector &nums) { int n = nums.size(); vector dp(n); dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < n; i++) { dp[i] = max(dp[i - 1] + nums[i], nums[i]); result = max(result, dp[i]); } return result; } };
三、编辑距离
判断子序列（LeetCode-392）
题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
思路
和最长公共子序列（LeetCode-1143）类似
五部曲
dp[i][j] 含义
长度为 [ 0 , i − 1 ] 的字符串s与长度为 [ 0 , j − 1 ]的字符串t的相同子序列长度
递推公式
如果 s [ i − 1 ] = t [ j − 1 ]
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1
如果二者不相等，沿用之前结果
d p [ i ] [ j ] = d p [ i ] [ j − 1 ]
数组初始化
dp[i][0] 与空串一起求最长公共子序列，自然为零
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(); int n2 = t.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i][j - 1]; } } } return (dp[n1][n2] == n1 ? true : false); } };
我直接修改最长公共子序列（LeetCode-1143）的代码做的结果，实际上就是看最长公共子序列长度是否为s字符串长度，如果相等，即s为t的子序列
class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(); int n2 = t.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return (dp[n1][n2] == n1 ? true : false); } };
不同的子序列（LeetCode-115）
题目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
示例 2：
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
思路
五部曲
dp[i][j] 含义
以 i − 1为结尾的字符串s子序列中出现以 j − 1 为结尾的字符串t的个数
递推公式
如果 s [ i − 1 ] = t [ j − 1 ]
一种方法是用 s [ i − 1 ] 来匹配，个数为 d p [ i − 1 ] [ j − 1 ]
即使相等，就一定要用它匹配？举个例子 s : b a g g ，s [ 3 ] = s [ 2 ] ，可以选着用 s [ 3 ]进行匹配，也可以不选，那就是用 d p [ i − 1 ] [ j ]
如果二者不相等，肯定不能用 s [ i − 1 ]，所以 d p [ i ] [ j ] = d p [ i − 1 ] [ j ]
数组初始化
dp[i][0] 表示出现空字符串的个数，只有一种方法，就是全删，所以等于一
dp[0][j] 表示空字符串出现以 j − 1为结尾的字符串t的个数，只能为零
dp[0][0] 空字符串可以删除0个元素，出现空字符串t，所以为一
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int numDistinct(string s, string t) { int n1 = s.size(); int n2 = t.size(); if (n1 < n2) { return 0; } vector> dp(n1 + 1, vector(n2 + 1)); dp[0][0] = 1; for (int i = 0; i < n1; i++) { dp[i][0] = 1; } for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n1][n2]; } };
两个字符串的删除操作（LeetCode-583）
题目
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco" 输出：4
提示：
1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母
思路
五部曲
dp[i][j] 含义
以 i − 1为结尾的字符串word1和以 j − 1 为结尾的字符串word2想要相等，需要删除元素的最小次数
递推公式
如果 w o r d 1 [ i − 1 ] = w o r d 2 [ j − 1 ]
次数为 d p [ i − 1 ] [ j − 1 ]
如果二者不相等，有下述三种情况
删除 w o r d 1 [ i − 1 ] ，最少操作次数为 d p [ i − 1 ] [ j ] + 1
删除 w o r d 2 [ j − 1 ] ，最少操作次数为 d p [ i ] [ j − 1 ] + 1
二者取最小值
数组初始化
dp[i][0] word2为空字符串，明显等于 i
dp[0][j] word1为空字符串，明显等于 j
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { dp[i][0] = i; } for (int j = 1; j <= n2; j++) { dp[0][j] = j; } for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[n1][n2]; } };
编辑距离（LeetCode-72）
题目
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
思路
五部曲
dp[i][j] 含义
将 i − 1为结尾的字符串word1转换为 j − 1 为结尾的字符串word2，最少操作数为 d p [ i ] [ j ]
递推公式
如果 w o r d 1 [ i − 1 ] = w o r d 2 [ j − 1 ]
不进行任何操作，值为 d p [ i − 1 ] [ j − 1 ]
如果二者不相等，有下述三种情况
首先要清楚word2添加一个元素，等价于word1删除一个元素！二者操作次数也均为一次！
操作一：word1删除一个元素，最少操作次数为 d p [ i − 1 ] [ j ] + 1
操作二：word2删除一个元素，最少操作次数为 d p [ i ] [ j − 1 ] + 1
操作三：word1替换一个元素，最少操作次数为 d p [ i − 1 ] [ j − 1 ] + 1
三者取最小值
数组初始化
dp[i][0] 明显等于 i
dp[0][j] 明显等于 j
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector> dp(n1 + 1, vector(n2 + 1)); for (int i = 1; i <= n1; i++) { dp[i][0] = i; } for (int j = 1; j <= n2; j++) { dp[0][j] = j; } for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1}); } } } return dp[n1][n2]; } };
四、回文
回文子串（LeetCode-647）
题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
思路
五部曲
dp[i][j] 含义
区间范围为 [ i , j ]（注意左右都是闭区间）的子串是否为回文子串，元素类型为布尔类型
递推公式
当 s [ i ] ≠ s [ j ] 时，元素值必为 f a l s e
当 s [ i ] = s [ j ] 时，分三种情况
情况一：i = j ，即二者下标相等，都指向同一个字符，肯定是回文子串
情况二：i 和 j 下标相差 1 ，例如 a a ，也是回文子串
情况三：二者下标相差大于一，那必须看区间 s [ i + 1 , j − 1 ]是不是回文子串
数组初始化
初始值全为 f a l s e
遍历顺序
要注意看当前元素依靠谁的状态获取，看到前文情况三，就知道肯定对于 i ii 的遍历肯定要倒序。
代码展示
class Solution { public: int countSubstrings(string s) { int n = s.size(); vector> dp(n, vector(n, false)); int result = 0; for (int j = 0; j < n; j++) { for (int i = j; i >= 0; i--) { if (s[i] == s[j]) { if (j - i <= 1) { dp[i][j] = true; result++; } else { if (dp[i + 1][j - 1]) { dp[i][j] = true; result++; } } } } } return result; } };
最长回文子序列（LeetCode-516）
题目
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成
思路
五部曲
dp[i][j] 含义
在区间范围为 [ i , j ] （注意左右都是闭区间）内的最长的回文子序列的长度
递推公式
当 s [ i ] ≠ s [ j ]时，只说明二者不能同时加入回文子串，可以分别加入求最大值，d p [ i ] [ j ] = m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] )
当 s [ i ] = s [ j ] 时，d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] + 2
数组初始化
当下标 i = j时，即一个字符的回文子序列长度应该为一
遍历顺序
要注意看当前元素依靠谁的状态获取，看到递推公式，就知道肯定对于 i的遍历肯定要倒序。
代码展示
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); if (n == 1) { return 1; } vector> dp(n, vector(n)); for (int i = n - 2; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } };
七、天道酬勤
从年后开始，每天一小时，前后花费差不多一个月的时间把卡尔哥的动态规划专题刷了一遍，受益良多。但套路是会了，碰到新题目效果如何，我心里还是犯嘀咕的，明天开始刷一个月蓝桥杯，也算是成果的检验了。
