动态规划
2019-05-12 本文已影响1人
别时茫茫
动态规划
标签（空格分隔）： algorithm
作业部落地址：https://www.zybuluo.com/LIUHUAN/note/1465029
最长连续递增子序列
- 最长连续递增子序列
- 题目大意：在一个数字序列中找到最长的且连续的递增子序列的长度。
- 例如：序列：[1,3,5,4,7] 最长连续子序列长度为3，即[1,3,5]
- 又如: 序列：[2,2,2,2,2] 最长连续子序列长度为1，即[2]
1、思路一
- 计算每个元素开始或者结束的连续子序列，记录最大的值
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1)
return n;
int maxlen = 1;
for(int i = 0; i < n;i++ ) {
int len = 1;// 每次nums[i] 开始的序列最大长度为1,往后增长
for(int j = i+ 1;j < n;j++){
if(nums[j] > nums[j-1] ) {// 连续递增
len += 1; // 长度增加
maxlen = max(maxlen,len);
}else {// 不连续递增了，下一个元素继续计算
break;
}
}
return maxlen;
}
2、思路2
- 假设我们知道了某个元素结尾的最长连续子序列的长度，那么下一个元素，要么比其前一个元素大，一起构成更长的一个连续子序列，要么自己独自成一个子序列长度为1。
- 假设我们有dp[i] 表示以nums[i]结尾元素的最长连续子序列长度
- 那么下一个元素nums[i+1] 与nums[i] ，要么nums[i+1] > nums[i] 这时可以构成一个更长的连续递增子序列且以nums[i+1]结尾，长度为dp[i] + 1。要么nums[i+1] <= nums[i]，这时以nums[i+1]结尾的最长连续子序列长度为1.
- 初始状态是：dp[0] = 1
- 综合上述两种情况，可以得到如下的表达式
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1)
return n;
vector<int> dp(n,1);
int maxlen = 1;
for(int i = 1; i < n; i++ ) {
if( nums[i] > nums[i-1] ) {
dp[i] = dp[i-1] + 1 ;
}
maxlen = max( dp[i] , maxlen );
}
return maxlen;
}
- 时间复杂度：O(n)，空间复杂度：O(n)
- 由于只需要获取最长的长度，所以这里可以优化空间复杂度
最长递增子序列
- 最长递增子序列
- 题目的意思是：在一个数字序列中找到最长的且是递增的子序列，返回这个最长子序列的长度
- 与上一个不同的是，这里的序列不需要是连续的
- 例如：[10,9,2,5,3,7,101,18] 序列的最长递增子序列为[2,3,7,101]
1、思路1
- 由上一题的思路可以知道，如果知道nums[i] 结尾的最长递增子序列为dp[i] 那么，以nums[i+1] 结尾的最长子序列，肯定是i+1前面的某个子序列（可能为空）以num[k]结尾，加上nums[i+1]构成的。也可以从另一个角度理解，如果i+1前面的某个数nums[k] 小于nums[i+1] 那么，{nums[k],nums[i+1]}可以构成一个比原来更长的子序列。
- 初始状态：dp[0] = 1
- 综合上述说明：可以得到如下的递推公式
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1 )
return n;
vector<int> dp(n,1);// 初始化为1
int max_len = 1;
for(int i = 1 ;i < n; i++) {
for(int j = i-1 ;j >=0 ;j-- ) { // 遍历[0,i-1]的元素加上nums[i] 之后的长度是否构成更长的递增子序列
if(nums[j] < nums[i]) {
dp[i] = max(dp[i],dp[j] + 1 );
max_len = max(max_len,dp[i]);
}
}
}
return max_len;
}
- 时间复杂度：O(
)，空间复杂度:O(n)
最长递增子序列的数量
- 最长递增子序列的个数
- 题目大意：在第二题的基础上，找到所有长度等于最大长度的递增子序列的长度的个数
- 例如：[1,3,5,4,7]，最长递增子序列的个数为2， 即，[1, 3, 4, 7] 和 [1, 3, 5, 7]。又如：[2,2,2,2,2],最长递增子序列的个数为5，所有的长度为1的序列都是最长递增子序列
1、思路1
- 上一题中记录了最长递增子序列的长度。并没有记录这个长度的子序列的个数
- 所以我们通过计算每一个元素为结尾的最长递增子序列的来源个数，来获得最大长度递增子序列的个数
- 具体的来说，假设f[i]表示以nums[i]结尾的元素的最长子序列个数，dp[i]表示以nums[i]结尾的最长子序列的长度，那么找到最长的子序列长度dp[k],就可以找到其对应的长度来源的个数f[k]。那么f[k]如何计算呢？
- f[k] 依赖于dp[k]，如果dp[k]是从dp[m]扩展而来，那么f[k] = f[m],如果dp[k] 还可以从dp[x]扩展而来，那么f[k] = f[m] + f[x]...可以看出来，f[k]等于能够从之前的某个子序列扩展到dp[k]而来的所有序列个数之和。
- 得到如下的公式:
- 初始情况：dp[i] =1,f[i]=1;
- 最后需要依据最大长度的递增子序列求和所有的来源个数。
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1)
return n;
vector<int> dp(n,1); // nums[i]结尾的最长递增子序列长度
int max_len = 1;//最大长度
vector<int> max_c(n,1);// 每个最长子序列的长度默认为1
for(int i = 1; i < n; i++ ){
for(int j = i - 1; j >= 0; j-- ) {
if(nums[i] > nums[j]) {
if(dp[i] < dp[j] + 1){// dp[i] 可以从dp[j] 扩展得到更长的子序列，那么最长子序列的个数就是扩展前dp[j]的个数，max_c[j]
max_c[i] = max_c[j]; // 扩展后的来源个数
}else if(dp[i] == dp[j] + 1) { // 相同长度的其他扩展而来的子序列
max_c[i] += max_c[j] ; // 因为长度相同，所以求和来源的个数
}
dp[i] = max(dp[i],dp[j] + 1);
max_len = max(dp[i],max_len);
}
}
}
// 遍历所有的dp[i]等于最大长度时，求和所有的max_c[i]，得到最大长度递增子序列的个数和
int maxc = 0;
for(int i = 0; i < n ; i++) {
if(dp[i] == max_len) {
maxc += max_c[i];
}
}
return maxc;
}
- 时间复杂度：O(
最长配对链
- 最长配对链
- 题目大意：给定元素为两个数的元组的数组，元组的属性(a,b) a < b，如果两个元素x=(a,b),y=(c,d) 满足b<c 那么(x,y)构成一个链，长度为2，这个题求的是所有元素中能够成这个链的最大长度。其中元素序列可以任意选取。
思路1
- 本题与最长递增子序列非常相似，不同点在于，这里可以随意选取元素，构成组合，如果按照元组的第一个元素排序，就能够得到和最长递增子序列的问题一致的情况。
- 初始情况：dp[i] = 1;
int findLongestChain(vector<vector<int>>& pairs) {
int n = pairs.size();
if(n <= 1)
return n;
sort(pairs.begin(),pairs.end(),[](vector<int>& a,vector<int>&b ){return a[0] < b[0];});
vector<int> dp(n,1);
int max_len = 1;
for(int i =1;i < n; i++) {
int ifirst = pairs[i][0];
for(int j =i -1 ;j >= 0; j--) {
if(pairs[j][1] < ifirst) { // 构成递增链
dp[i] = max(dp[i],dp[j] + 1); //更新递增链大小
max_len = max(max_len,dp[i]);
}
}
}
return max_len;
}
- 时间复杂度：O(
