目录
写在前面数字三角形最长上升子序列最长上升子序列 II最长公共子序列写在前面
之前讲过背包问题,不知道大家忘了吗,如果忘了可以点这里,这次是线性DP
数字三角形
状态表示:f[i,j],到点i,j的最大路径
状态计算:f[i,j] = MAX(f[i-1,j-1]+a[i,j],f[i-1,j]+a[i,j])
看图,以例题为例,将它看成五行五列的三角形,每个点都可以用坐标表示。那么我们可以得知到一个数的最大路径要么来自左上,要么来自右上。左上的数用f[i-1,j-1]表示,右上的数f[i-1,j]表示,因此我们就有了状态转移公式:
f[i,j] = MAX(f[i-1,j-1]+a[i,j],f[i-1,j]+a[i,j])
所以就有了最终的代码:
#include#include using namespace std; const int N = 510, INF = 1e9; int n; int a[N][N]; int f[N][N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) scanf("%d", &a[i][j]); for (int i = 0; i <= n; i ++ ) for (int j = 0; j <= i + 1; j ++ )//注意这里j从0到i+1,因为对于边界点,它的上一层只有一条路径通向它 f[i][j] = -INF;//初始化近似为-∞ f[1][1] = a[1][1]; for (int i = 2; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]); int res = -INF; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); printf("%d\n", res); return 0; }
最长上升子序列
状态表示:f[i]表示从第一个数字开始算,以w[i]结尾的最大的上升序列。(以w[i]结尾的所有上升序列中属性为最大值的那一个)
状态计算(集合划分):j∈(0,1,2,…,i-1), 在w[i] > w[j]时,
f[i] = max(f[i], f[j] + 1)。
有一个边界,若前面没有比i小的,f[i]为1(自己为结尾)。
最后在找f[i]的最大值。
时间复杂度
O(n2) 状态数(n) * 转移数(n)
看图, 首先 f[i]f[i] 的含义是以 w[i]结尾的最长上升子序列的长度
初始值 f[i]=1,i∈[0,n−1],表示自己就是最长上升子序列,长度为 1
接下来考虑状态转移,把前 i−1个数字中所有满足条件 w[j] 会发现II的数据范围变了,那我们就得做优化,怎么优化呢? 状态表示:f[i]表示长度为i的最长上升子序列,末尾最小的数字。(长度为i的最长上升子序列所有结尾中,结尾最小min的) 即长度为i的子序列末尾最小元素是什么。 状态计算:对于每一个w[i], 如果大于f[cnt-1] (下标从0开始,cnt长度的最长上升子序列,末尾最小的数字),那就cnt+1,使得最长上升序列长度+1,当前末尾最小元素为w[i]。 若w[i]小于等于f[cnt-1],说明不会更新当前的长度,但之前末尾的最小元素要发生变化,找到第一个 大于或等于 (这里不能是大于) w[i],更新以那时候末尾的最小元素。 f[i]一定以一个单调递增的数组,所以可以用二分法来找第一个大于或等于w[i]的数字。 时间复杂度 O(nlogn)状态数(n) * 转移数(logn) 集合表示:f[i][j]表示a的前i个字母,和b的前j个字母的最长公共子序列长度 集合划分:以a[i],b[j]是否包含在子序列当中为依据,因此可以分成四类: max=f[i−1][j−1] 看似是max=f[i−1][j] , 实际上无法用f[i−1][j]表示,因为f[i−1][j]表示的是在a的前i-1个字母中出现,并且在b的前j个字母中出现,此时b[j]不一定出现,这与条件不完全相等,条件给定是a[i]一定不在子序列中,b[j]一定在子序列当中,但仍可以用f[i−1][j]来表示,原因就在于条件给定的情况被包含在f[i−1][j]中,即条件的情况是f[i−1][j]的子集,而求的是max,所以对结果不影响。 例如:要求a,b,c的最大值可以这样求:max(max(a,b),max(b,c))虽然b被重复使用,但仍能求出max,求max只要保证不漏即可。 实际上,在计算时,①包含在②和③的情况中,所以①不用考虑 到此这篇关于C语言深入探究动态规划之线性DP的文章就介绍到这了,更多相关C语言 线性DP内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!#include
最长上升子序列 II
#include
最长公共子序列
#include
X 关闭
X 关闭
- 15G资费不大降!三大运营商谁提供的5G网速最快?中国信通院给出答案
- 2联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 3亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 4现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 5如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 6AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 7转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 8充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 9好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 10名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?