【动态规划】 LIC&LCS

这篇具有很好参考价值的文章主要介绍了【动态规划】 LIC&LCS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前段时间再次复习并加深了 LIS 和 LCS 的内容,于是便来写一篇总结。

朴素做法

首先当然是 O ( n 2 ) O(n^2) O(n2) 的做法。直接把代码放在这里。

最长上升子序列:

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10;
int n,ans=0;
int a[N],dp[N];
//dp[i]表示以a[i]结尾的最长上升子序列的长度
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=1;
	for(int i=1;i<=n;i++){ 
		for(int j=1;j<i;j++){
			if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
            //a[j]<a[i],即可以转移,就从dp[j]转移过来并且长度+1 
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

最长公共子序列:

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
int n,m,ans=0;
int a[N],b[N],dp[N][N];
//dp[i][j]表示到a串的第i位和b串的第j位的最长公共子序列的长度
int main(){
	scanf("%d",&n);
	m=n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			//先继承上一个状态 
			if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			//如果i,j两个相同,就从dp[i-1][j-1]转移,并且长度+1 
		}
	}
	printf("%d\n",dp[n][m]);
	return 0;
}

对于 O ( n 2 ) O(n^2) O(n2) 的做法就不再赘述了。

进阶做法

O ( n 2 ) O(n^2) O(n2) 的做法时空复杂度都太高了,所以讲解一个 O ( n l o g n ) O(nlogn) O(nlogn) 的做法。

最长上升子序列

二分法

首先考虑朴素做法,对于 a i a_i ai 枚举 1 1 1 ~ i − 1 i-1 i1 的所有数,如果符合条件(即小于 a i a_i ai )则进行转移。
但是显然这个枚举的过程很没有必要,那么怎样进行最高效的查找?
答案是二分

我们处理一个 d d d 数组, d i d_i di 表示长度为 i i i 的上升子序列的最小结尾元素
那么怎样去维护呢?
每一次得到一个数,就在 d d d 数组中二分查找到第一个比 a i a_i ai 大的位置,将 d p i dp_i dpi 的值改为查找到的 d d d 数组的下标,也就是答案。
若没有比 a i a_i ai 大的值,就将最大长度加一然后添加在 d d d 数组的末尾即可

原理:
对于每一个数,原本的朴素做法是在前面所有数中找到符合条件的最大转移值,此二分做法首先满足顺序问题,其次,对于找到第一个比自己大的,就在这个位置更新可以理解为:找到的比自己大的位置的前一个位置的值一定比现在的数小,那么就从前一个位置转移过来,长度加一,又结合 d d d 数组的含义,更新就在下一个位置,也就是查找到的这个位置更新。
怎样保证正确性,一定是最优的?因为找到的这个位置满足的条件是“比当前的数大”,也就是说,这个位置的上升子序列的末尾字符一定是大于我当前可以转移过来的字符,那么为了使后面的数转移的时候可以以最优的方案转移过来,那么就把更小的更新到这个位置,也就是我现在的这个数。
一个简单的例子:
【动态规划】 LIC&LCS,动态规划,动态规划,算法

对于图中标红的数字,可以看到是代替了前一个在该位置上的更大的数值,而对于蓝色的数字,则是因为前面标红数字的代替才得到了最优解的位置。
试想一下,如果最后加入的 5 5 5 之前 4 4 4 并没有替代 6 6 6 ,那么 5 5 5 就不可以出现在第四个位置上,也无法得到正确答案了。

还有一个问题,如何保证 d d d 数组一定是递增的?
从做法角度思考,每次用二分查找比当前大的数再代替或添加,一定是递增的。
从上升子序列的性质来想,使用反证法:
若满足一个 j < i j<i j<i d j > d i d_j>d_i dj>di ,则说明有一个长度更小却末尾值更大的上升子序列,但是因为上升子序列是单调递增的,以 d i d_i di 结尾的上升子序列中一定有一个位置 k k k 满足 s k < d i s_k<d_i sk<di (假定 s s s 数组为以 d i d_i di 结尾的上升子序列,此处只做证明辅助作用)且 k = j k=j k=j ,那么则 s k < d i < d j s_k<d_i<d_j sk<di<dj ,根据 d d d 数组的含义可知, s k s_k sk 一定是优于 d j d_j dj 的,则假设不成立,所以 d d d 数组一定是单调递增的。

那么到此,整个问题就解决了。
c o d e : code: code:

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10;
int n,maxn=0;
int a[N],d[N],dp[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	maxn=1;
	d[1]=a[1];
	for(int i=2;i<=n;i++){ 
		if(a[i]>d[maxn]) d[++maxn]=a[i];
		else{
			int j=lower_bound(d+1,d+1+maxn,a[i])-d;
			d[j]=a[i];
			dp[i]=j; 
		}
	}
	printf("%d\n",maxn);
	return 0;
}

树状数组法

还是结合朴素做法,发现转移条件是下标比当前小且值比当前小,显然是一个二维偏序
同样的,前面加入的顺序是没有问题的,只需要满足权值小就行了,由此可以使用树状数组,在 a i a_i ai 位置放 d p i dp_i dpi,求出前缀最大值就可以转移了。
个人认为这个做法比二分好理解一些,并且后面的应用也会稍多一些。

c o d e : code: code:

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,maxn=0,maxnum=0;
int a[N],dp[N],c[5000000];

int lowbit(int x){return (x&(-x));}
void change(int x,int y){
	for(int i=x;i<=maxnum;i+=lowbit(i)) c[i]=max(c[i],y);
	return ;
}
int query(int x){
	int val=0;
	for(int i=x;i;i-=lowbit(i)) val=max(val,c[i]);
	return val;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
	    scanf("%d",&a[i]);
	    a[i]+=10000;//若有a[i]为负数的情况,需要全部上调
	    maxnum=max(maxnum,a[i]);
	}
	for(int i=1;i<=n;i++){
		dp[i]=query(a[i]-1)+1;
		change(a[i],dp[i]);
		maxn=max(maxn,dp[i]);
	}
	printf("%d\n",maxn);
	return 0;
}

最长公共子序列

实际上将公共子序列转化为最长上升子序列即可。
首先考虑公共子序列成立的条件:

  • 两个序列中均有
  • 在两个序列中均是按顺序的

我们先将两个序列都有的数值处理出来,接下来只需考虑顺序问题。
做法是:
对于每一个在 a a a 序列中出现的数,处理出其在 a a a 序列中的位置。再遍历 b b b ,对于 b i b_i bi ,如果在 a a a 中出现过,那么就加入一个新的序列,加入的值是之前处理的这个值在 a a a 中的位置。
最后在这个新的序列中求出最长上升子序列的长度即可。
做法的正确性?
首先,因为加入新序列的条件是在两个序列中都出现,满足第一个条件;
其次,我们加入新序列的顺序是按照 b b b 中的顺序,而加入的值则是在 a a a 中的顺序,求出最长上升子序列,正是保证了其在 a a a 中一定是有序的。
举一个简单的例子:
【动态规划】 LIC&LCS,动态规划,动态规划,算法
这样就很好理解了。文章来源地址https://www.toymoban.com/news/detail-799042.html

到了这里,关于【动态规划】 LIC&LCS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 动态规划经典案例解析之最长公共子序列(LCS)_窥探递归和动态规划的一致性

    动态规划处理字符相关案例中,求 最长公共子序列 以及求 最短编辑距离 ,算是经典中的经典案例。 讲解此类问题的算法在网上一抓应用一大把,即便如此,还是忍不住有写此文的想法。毕竟理解、看懂都不算是真正掌握,唯有瞧出其中玄机,能有自己独有的见解和不一样

    2024年02月13日
    浏览(37)
  • 【算法】动态规划 ⑧ ( 动态规划特点 )

    求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ; 求最值 : 最大值 , 最小值 等 ; 大规模问题的结果 由 小规模问题 的计算结果 取最大值 大规模问题的结果 由 小规模问题 的计算结果 取最小值 可行性 : 是否可行

    2023年04月08日
    浏览(46)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(44)
  • 60题学会动态规划系列:动态规划算法第三讲

    简单多状态问题 文章目录 一.按摩师 二.打家劫舍系列 三.删除并获得点数 四.粉刷房子 力扣链接:力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,

    2024年02月08日
    浏览(48)
  • 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )

    动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ; 具体的算法都有具体的步骤 , 如 : 二分法 , 其 有固定的解决步骤 , 先取一个中心点 , 判断解在左边还是右边 , 然后在一边再取一个中心点 , 再进行判定 , 该算法有具体的步骤 ; 动态规划

    2024年01月16日
    浏览(45)
  • 60题学会动态规划系列:动态规划算法第二讲

    都是路径问题~ 文章目录 1.不同路径 2.不同路径II 3.礼物的最大价值 4.下降路径最小和 5.最小路径和 力扣链接:力扣 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在

    2024年02月07日
    浏览(59)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(34)
  • 60题学会动态规划系列:动态规划算法第五讲

    子数组系列题目 文章目录 1.最大子数组和 2.环形子数组的最大和 3.乘积最大数组 4.乘积为正数的最长子数组长度 5.等差数列划分 6.最长湍流子数组 7.单词拆分 8.环绕字符串中唯一的子字符串 力扣链接:力扣 给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(

    2024年02月15日
    浏览(55)
  • 60题学会动态规划系列:动态规划算法第一讲

    坚持就是胜利 - -  文章目录 1.第N个泰波那切数 2.三步问题 3.使用最小花费爬楼梯 4.解码方法 力扣链接:力扣 泰波那契序列 Tn 定义如下:  T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数  n ,请返回第 n 个泰波那契数 Tn 的值。  首先我们分析一下

    2024年02月06日
    浏览(44)
  • 【动态规划】动态规划算法基本概念,原理应用和示例代码

             动态规划(Dynamic Programming,简称DP)是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题,通过解决子问题只需解决一次并将结果保存下来,从而避免了重复计算,提高了算法效率。         通俗来讲,动态规划算法是解决一类具有重叠

    2024年01月21日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包