动态规划中子序列也一直是高频考点，在一条子序列内部操作（递归数组为一维），也有在两条子序列内部操作（递归数组为二维）。
首先回顾一下动态规划五部曲：
- 1 定义递归数组
- 2 推导递归公式
- 3 初始化递归数组
- 4 确定遍历顺序
- 5 手动打印数组检查是否正确
首先我们先来两个开胃小菜题目，了解一下子序列类动态规划题目如何下手。
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
- 1 定义dp[i]为包含第i个元素的最大和
- 2 dp[i] = max(dp[i-1]+nums[i], nums[i])
- 3 dp[0] = nums[0]
- 4 i从1到nums.size()
以下为代码：
class Solution {
public:
int maxSubArray(vector& nums) {
int m = nums.size();
vector dp(m);
dp[0] = nums[0];
int result = dp[0];
for(int i = 1; i<m; i++)
{
dp[i] = max(dp[i-1]+nums[i], nums[i]);
if (result < dp[i]) result=dp[i];
}
return result;
}
};
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
- dp[i][0]为最大子数组乘积最大值，dp[i][1]为最大子数组乘积的最小值。
- 递归表达式
dp[i][0] = max(max(dp[i-1][0] * nums[i], dp[i-1][1]*nums[i]), nums[i]);dp[i][1] = min(min(dp[i-1][0] * nums[i], dp[i-1][1]*nums[i]), nums[i]);
- 初始化：dp[0][0] = dp[0][1] = nums[0];
class Solution {
public:
int maxProduct(vector& nums) {
int m = nums.size();
vector<vector> dp(m, vector(2, 0));
dp[0][0] = nums[0];
dp[0][1] = nums[0];
int result = nums[0];
for(int i=1; i<m; i++)
{
dp[i][0] = max(max(dp[i-1][0] * nums[i], dp[i-1][1]*nums[i]), nums[i]);
dp[i][1] = min(min(dp[i-1][0] * nums[i], dp[i-1][1]*nums[i]), nums[i]);
result = max(result, dp[i][0]);
}
return result;
}
};
开题介绍
好了，开胃小菜结束了，怎么样，是不是很有继续下去的冲动，不要着急，我们从宏观入手，先了解大概会出现哪些题目，然后细细深入，理解每一个题目。
题目分类：
- 1 递增子序列
- 最长连续递增子序列
- 最长递增子序列
- 2 公共子序列
- 最长重复子数组
- 最长公共子序列
- 判断子序列
- 不同的子序列
- 3 序列的删除操作
- 两个字符串的删除操作
- 编辑距离
- 4 其他
- 摆动序列
- 整数求和
- 完全平方数
========================递增子序列=====================
最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
一般来说连续比不连续要好做很多。本题需要最长连续递增子序列的长度，只需要判断第i个元素比第i-1个元素大，即可+1。同时遍历初始化第一个元素，从第二个元素开始遍历。代码如下：
class Solution {
public:
int findLengthOfLCIS(vector& nums) {
int m = nums.size();
if (m <= 1) return m;
int result = 0;
vector dp(m, 1);
for(int i=1; i nums[i-1])
{
dp[i] = dp[i-1] + 1;
}
if (result < dp[i]) result=dp[i];
}
return result;
}
};
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
不连续他来了，比起连续来说，不连续的子序列需要第i个元素返回去看0到i-1的元素和第i个元素的关系。大家可以体会一下，代码如下：
class Solution {
public:
int lengthOfLIS(vector& nums) {
int m = nums.size();
if (m <= 1) return m;
vector dp(m, 1);
int result = 0;
for(int i = 1; i<m; i++)
{
for(int j=0; j<i; j++)
{
if (nums[i]>nums[j]) dp[i] = max(dp[i], dp[j]+1);
}
if (result < dp[i]) result = dp[i];
}
return result;
}
};
========================公共子序列=====================
最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
子数组：连续；子序列：不连续。这一般是题目的提示，大家记得get到。
该题比上述题目区别的地方在于，输入为两个子数组或者字符串，如果想实现比较，需要创建一个二维递归数组。
- 递归数组定义：定义dp[i][j]为nums1[:i]数组与nums2[:j]数组的公共最长子数组长度
- 递归方程：dp[i][j] = dp[i-1][j-1]+1
- 初始化：全体初始化为0
- 遍历：注意细节，为了方便处理dp数组的i=0的该行和j=0的一列不做单独处理，i，j都从1开始遍历，同时dp数组的索引i，j都需要-1.
class Solution {
public:
int findLength(vector& nums1, vector& nums2) {
int m = nums1.size()+1;
int n = nums2.size()+1;
vector<vector> dp(m, vector(n, 0));
int result = 0;
for(int i=1; i<m; i++)
{
for(int j=1; j<n; j++)
{
if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
if (result < dp[i][j]) result = dp[i][j];
}
}
return result;
}
};
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
子数组：连续；子序列：不连续。这一般是题目的提示，大家记得get到。
当寻找的子序列，最大的区别在于递归方程。
此时我们可以认为dp[i][j]的最大子序列的长度为（text1删除第i个元素与text2的最大子序列的长度）与（text1与text2删除第j个元素的最大子序列的长度）
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length() +1 ;
int n = text2.length() + 1;
vector<vector> dp(m, vector(n, 0));
int result = 0;
for(int i=1; i<m; i++)
{
for(int j=1; j<n; j++)
{
if (text1[i-1]==text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (result < dp[i][j]) result = dp[i][j];
}
}
return result;
}
};
判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
该题与上题一致，只是递归方程中只能删减长序列的元素。最后最大长度如果等于短字符串的长度，则说明短字符串为长字符串的子序列。
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size() + 1;
int n = t.size() + 1;
vector<vector> dp(m, vector(n, 0));
for(int i=1; i<m; i++)
{
for(int j=1; j<n; 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[m-1][n-1] == m-1;
}
};
========================序列的删除操作=====================
两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
- 递归数组定义：如上
- 递归方程：最小步数 = 第一个单词删除一个元素 ， 第二个单词删除一个元素，两个单词都删除元素。
- 初始化：如上
- 遍历顺序：如上
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size() + 1;
int n = word2.size() + 1;
vector<vector> dp(m, vector(n, 0));
for(int i=0; i<m; i++) dp[i][0] = i;
for(int j=0; j<n; j++) dp[0][j] = j;
for(int i=1; i<m; i++)
{
for(int j=1; j<n; j++)
{
if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+2);
}
}
return dp[m-1][n-1];
}
};
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
针对操作数来说，对word1进行插入字符操作，等价于word2进行删除操作。
针对操作数来说，对word1进行替换字符操作，等价于word1和word2都进行删除操作，但是只能当做1次操作。
针对操作数来说，对word1的操作数也等于word2的操作数。
故，针对操作数来说，本来可以针对2个单词都可以进行的操作可以被规约为只对word1进行操作，同时将插入、删除、替换都变成删除操作。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size() + 1;
int n = word2.size() + 1;
vector<vector> dp(m, vector(n, 0));
for(int i=0; i<m; i++) dp[i][0] = i;
for(int j=0; j<n; j++) dp[0][j] = j;
for(int i=1; i<m; i++)
{
for(int j=1; j<n; j++)
{
if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
// 插入 删除 替换
else dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);
}
}
return dp[m-1][n-1];
}
};
========================其他=====================
摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
该题最大的难点在于递归数组的定义。
在此我们总结一下递归数组的定义的几种形式：
- 1 一维数组
- 2 二维数组（每一个元素N个状态）
- 3 三维数组（每一个元素1个状态）
递归数组定义：本题考查摆动序列，摆动即说明单个元素可能存在多个状态，即波峰和波谷状态。
递归方程：如果第i个元素小于第i-1元素，则第i个元素的波谷所拥有的子序列摆动长度+1，反之，则第i个元素的波峰所拥有的子序列摆动长度+1。
大家好好琢磨，代码如下：
class Solution {
public:
int wiggleMaxLength(vector& nums) {
vector<vector> dp(1000, vector(2, 1));
for(int i=1; i<nums.size(); i++)
{
for(int j=0; j<i; j++) { if (nums[i] > nums[j]) dp[i][0] = max(dp[i][0], dp[j][1]+1);
else if(nums[i] < nums[j]) dp[i][1] = max(dp[i][1], dp[j][0]+1);
}
}
return max(dp[nums.size()-1][0], dp[nums.size()-1][1]);
}
};
整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
递归数组定义：dp[i]为整数i拆分的乘积最大化。
递归数组：dp[i] = max(max(j*(i-j), j*dp[i-j]), dp[i]) 有两种选择，拆或者不拆。
递归初始化：由于n>=2，故dp[2]=1（2=1+1；1*1=1）。
递归顺序：使用两个循环是因为，第一个循环为i，第二个循环为拆多少。由于n>=2，则i从3开始。
class Solution {
public:
int integerBreak(int n) {
// 1 定义动规矩阵
vector dp(n+1);
// 3 初始化
dp[2] = 1;
// 2 动规方程
for (int i=3; i<=n; i++)
{
for (int j=1; j<i; j++)
{
dp[i] = max(max(j*(i-j) , j*dp[i-j]), dp[i]);
}
}
return dp[n];
}
};
完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
动规数组的定义：dp[i]为整数i的完全平方数的最少数量。
动规方程：循环j可以先找到i内上一个最小的dp[i-j*j]，则dp[i] = 1 + min(dp[i-j*j])，示例
- dp[26] = dp[16] + dp[10] = 1 + dp[10]
- dp[10] = dp[9] + dp[1] = 1 + dp[1]
- dp[1] = 1
- dp[26] = 1 + dp[10] = 1 + 1 +dp[1] = 1+1 +1 = 3
初始化：全部为0。
遍历顺序：第一个循环为了生成必要的前置状态，第二个循环为了找到最小的dp[i-j*j]
以下为代码：
class Solution {
public:
int numSquares(int n) {
vector dp(n+1, 0);
for(int i=1; i<=n; i++)
{
int min_value = 1e9;
// 找最小数量的前置
for(int j=1; j*j <= i; j++)
{
min_value = min(min_value, dp[i-j*j]);
}
dp[i] = min_value + 1;
}
return dp[n];
}
};