1.300最长递增子序列
1.问题描述
找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
2.问题转换
从nums[0...i]的最长的递增的子序列
3.解题思路
- 每一个位置的nums[i]都有两种状态：是否放入
- 对于放入状态：找到从[0..j](j<i)之间的递增子序列，如果满足递增，放入子序列中，找到其中最长的那个递增子序列，更新长度。
- 对于不放入状态：如果不满足递增，则不放入。
4.为什么使用动态规划？
因为从[0..i]的最长的递增子序列状态一定是由[0..j]的状态递推出来，所以考虑使用动态规划的方法。
5.动态规划的具体实现
- dp[j]数组的含义：代表的是从nums[0..j]的最长递增子序列。
- 递推公式：for(int i = 0;i<j;i++){ if(nums[j]>nums[i]){//首先需要满足递增 dp[j] = max(dp[j],dp[i]+1);//从中选择最长的作为最长递增子序列.dp[i] +1:其中i可以等效为背包问题里面的j-weight[i],1可以等效为背包问题里面的value[i]. } }
- 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
- 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。
6.进阶：使用动态规划和二分法来解决
1.思路
我们使用一个数组tail用来存放从[0..i]的单调递增数组的尾数（而且对应的nums[i]越小越好），tail[i]代表的是尾数，i代表的是长度。
2.具体实现
1.遍历数组得到此时的nums[i],根据nums[i]在tail数组中找到能够满足的最左侧的位置。
2.最左侧的位置的查找：使用二分法来找到满足严格递增的最长的长度。可能会出现两种情况：
1.left<res(即在tails的范围内)当tails[mid]<nums[i],tails[left]>nums[i]:此时将tails[left] = nums[i],可以保证在后面运行的时候能够尽可能的找到更长的长度。
2.当left == res（即这个数比最右侧的那个递增的都长）。此时res++;tails[left] = nums[i].
3.最后的返回值就是对应的一个res的长度。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
/*//方法1：动态规划
int n = nums.size();
vector<int> dp(n,1);//dp[j]:从0-j数组的最长的递增子序列
int result = 1;
for(int j = 1;j<n;j++){
for(int i = 0;i<j;i++){
if(nums[j]>nums[i]){
dp[j] = max(dp[j],dp[i]+1);
}
}
if(result<dp[j])result = dp[j];
}
return result;
*/
//方法2：动态规划+二分查找
int n = nums.size();
vector<int> tails(n,0);//用来存放一个单调递增的数组的尾数
int res = 0;//代表的是单调递增的最大长度
for(auto num:nums){
//用于在tail数组中找到需要替换的那个位置tails[i]<num<tails[i+1],此时将其替换为tails[i+1] = num;
//如果这个值在这个里面找不到，就放在最右边,同时res++;
int left = 0,right = res;
while(left<right){//[left,right)循环不变量
int mid = left +(right - left)/2;
if(tails[mid]<num)left = mid+1;
else right = mid;
}
tails[left] = num;
if(res == right) res++;
}
return res;
}
};2.647最长连续递增子序列
1.问题描述
找到其中最长连续递增子序列的长度。
2.问题转换
从nums[0...i]的最长的连续递增的子序列
3.解题思路
- 每一个位置的nums[i]都有两种状态：是否放入
- 对于放入状态：nums[i]>nums[i-1],则放入。
- 对于不放入状态：如果不满足递增，则不放入。
4.为什么使用动态规划？
因为从[0..i]的最长的递增子序列状态一定是由前一个的状态递推出来，所以考虑使用动态规划的方法。
5.动态规划的具体实现
- dp[j]数组的含义：代表的是从nums[0..j]的最长连续递增子序列。（也可以将其表示为以i为结尾的最长的连续递增子序列，然后求解得到最大值）
- 递推公式：if(nums[i]>nums[i-1]){//满足递增才能添加
tail[i] = tail[i-1]+1;
}//if(result>tail[i])tail[i] = result;//比较找到最大值 - 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
- 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
//vector<int> dp(n,1);
vector<int> tail(n,1);
int result = 1;
int i = 0;
for(int i = 1;i<n;i++){
if(nums[i]>nums[i-1]){
tail[i] = tail[i-1]+1;
}
}
auto maxs = max_element(tail.begin(),tail.end());
return *maxs;
/*
for(int j = 1;j<n;j++){
i = j;
for(;i>0;i--){
if(nums[i]<=nums[i-1]){
break;
}
}
dp[j] = max(dp[j-1],(j-i+1));//长度
}
return dp[n-1];*/
}
};3.718最长重复子数组
1.问题描述
找到其中最长重复子数组的长度。
2.问题转换
按照顺序遍历，如果相同了就长度+1
3.解题思路
- 每一个位置的nums[i]都有两种状态：是否相等
- 对于相等状态：即nums1[i-1] == nums2[j-1],此时长度+1，然后比较最大值，更新res
- 对于不相等状态：比较最大值更新res
- 将最大值存放在res中
4.为什么使用动态规划？
因为每一个位置的值都可以由前面的状态或者当前的状态确定。
5.动态规划的具体实现
- dp[i][j]数组的含义：代表的是从nums1[0..i-1],nums2[0..j-1]的重复子数组长度。（
- 递推公式： if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}
- 初始化：默认情况下每个的都是1，因为自身可以当做唯一的那一个递增子序列。
- 遍历顺序：由递推公式可以知道，应该是满足从小到大的方式进行遍历。
- 最终结果存放在res中，因为res的含义是最长的重复子数组的长度。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int res = 0;
for(int i = 1;i<m+1;i++){
for(int j = 1;j<n+1;j++){
if(nums1[i-1] == nums2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}
if(dp[i][j]>res) res = dp[i][j];
}
}
return res;
}
};
