第五章——动态规划2

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

线性DP

数字三角形

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

像二维数组一样,设置行和列,只不过这里的列是斜着的,如圈出来的7,坐标可以表示为(4,2)

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

集合划分,所有路径可以分成俩类,某点左上方一类,右下方一类。

我们先把7去掉,左边计算的就是从起点到8路径的最大值,8的坐标是i-1,j-1,即左边状态可以表示为f[i-1,j-1]含义是从起点走到8这个位置的最大值,最后再给加7

右边计算也同理

f[i,j]=max(左边,右边)

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510,INF=1e9;
int n, m;
int a[N][N];//a存点
int f[N][N];//f数组表示状态
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++)
            f[i][j] = - INF;//给状态数组初始化
    f[1][1] = a[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 =2; i <= n; i++)
        res = max(res, f[n][i]);
    cout << res << endl;
    return 0 ;
}

最长上升子序列

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

该题1 2 5 6严格递增,所以输出是4

我们以第i-1个数来分类,第一个格子0,表示没有第i-1个数,即序列长度是1,之后分别是 i-1是第一个数,i-1是第2个数,i-1是第三个数……倒数第二个数是i-1

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

由于是上升子序列,aj<ai,aj在ai前面,设最后一个数是ai,倒数第二个数是aj,这样的最大长度上升子序列是f[j]+1,即以j为结尾的最大上升子序列+1

时间复杂度O(N^2)

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
const int N = 1010;
int n;
int a[N], f[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;//f[i]至少为1,即上升子序列只有一个数
        for (int j = 1; j < i; j++)//枚举到i的前一个数,所以这里不能是j<=i
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[i]);
    cout << res << endl;

    return 0;
}

把上述的最长序列保存下来

const int N = 1010;
int n;
int a[N], f[N],g[N];//g用来保存f[i]是由哪个状态转移来的
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;//f[i]至少为1,即上升子序列只有一个数
        g[i] = 0;
        for (int j = 1; j < i; j++)//枚举到i的前一个数,所以这里不能是j<=i
            if (a[j] < a[i])
                if(f[i]<f[j]+1)
                    {
                        f[i]=f[j]+1;
                        g[i] = j;//存一下f[i]是由哪个状态转移来的
                    }
    }
    int k=1;
    for (int i = 1; i <= n; i++)
        if (f[k] < f[i])
            k = i;//k记录最优解的下标
    printf("最大上升子序列长度:%d\n", f[k]);
    for (int i = 0, len = f[k]; i < len; i++)
    {
        printf("%d ", a[k]);
        k = g[k];
    }
    return 0;
}

最长公共子序列问题

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

这里abd满足条件,所以输出3。

f[i,j]表示的是第一个序列的前i个字母和第二个序列的前j个字母构成的公共子序列。

以a[i]和b[j]是否包含在子序列当中作为划分的依据。a[i]和b[j]选不选共有四种组合情况,我们划分成四个子集,00表示都不选,01不选a[i],选b[j],10选a[i],不选b[j],11俩个都选

00用f[i-1,j-1]来表示,因为f[i,j]没被选,a[i],b[j]没被选

11f[i-1,j-1]+1,去掉最后一组,最后给加回来

中间用f[i-1,j]和f[i,j-1]表示。一般不写00这个状态,因为后面的这些状态里包含该状态。

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
    scanf("%d %d", &n, &m);
    scanf("%s%s", a + 1, b + 1);//下标从1开始保存
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1]+1);
        }
    cout << f[n][m] <<endl;
    return 0;
}

石子合并

设有N堆石子排成一排,其编号为1,2,3,…,N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这N堆 石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2, 我们可以先合并1、2堆,代价为4,得到4 5 2, 又合并 1,2堆,代价为9,得到9 2 ,再合并得到11,总代价为4+9+11=24;
如果第二步是先合并2,3堆,则代价为7,得到4 7,最后一次合并代价为11,总代价为4+7+11=22。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
输入格式
第一行一个数N表示石子的堆数N。
第二行N个数,表示每堆石子的质量(均不超过1000)。
输出格式
输出一个整数,表示最小代价。
数据范围
1≤N≤300
输入样例:
4
1 3 5 2
输出样例:
22

我们以最后一次分界线的位置来分类,可以分成很多类。

含义:左边分一个,左边分2个,左边分3个......一直到k-1个

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档
第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

假设最后合并的是这俩堆,我们可以先将这俩堆去掉,因为无论怎么合并,最后都会合并这俩堆,即去掉最后一步求最大值

左边的最小代价+右边的最小代价+最后一步的代价。

最后一步的代价其实是第i堆到第j堆实际的总重量,最后一堆用前缀和表示为s[j]-s[i-1]。

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

最终结果从取最小值,k从i枚举到j-1

第五章——动态规划2,习题,动态规划,算法,Powered by 金山文档

时间复杂度:O(N^3)。文章来源地址https://www.toymoban.com/news/detail-594760.html

const int N = 310;
int n;
int s[N];//前缀和
int f[N][N];//状态
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i++)
        s[i] += s[i - 1];
    //按照从小到大枚举所有状态
    for(int len=2;len<=n;len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;//左右端点
            //如果只有一堆,和并不需要代价
            f[l][r] = 1e9;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    cout << f[1][n] <<endl;
    return 0;
}

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

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

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

相关文章

  • 60题学会动态规划系列:动态规划算法第五讲

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

    2024年02月15日
    浏览(55)
  • 云计算习题收录(第一章~第五章)

    转载:云计算习题 转载2:云计算试题 转载3:云计算试题(1~5章) 1 、云计算是对(    B  )技术的发展与运用。 A 并行计算      B  网格计算    C 分布式计算   D 三个选项都是 2、从研究现状上看,下面不属于云计算特点()。 A 超大规模  B 虚拟化  C 私有化  D 高可

    2024年02月02日
    浏览(53)
  • 算法基础课第五讲 动态规划

    时间复杂度:状态数量 转移的计算量 * 总体概述:给一堆物品,有体积有价值。有一个背包,在背包能装下的前提下最终能装下多少(背包不一定要装满) DP问题:一般需要从两方面考虑:状态表示以及状态计算 状态表示:f(i,j) 从两个方面考虑:集合(所有选法的集合)(

    2024年02月01日
    浏览(47)
  • <算法学习>动态规划练习题

    本篇文章为初学动态规划时的练习题。参考优质博客学习后根据伪代码描述完成代码。记录一下用于以后复习。 给定一个有n行数字组成的数字三角形. 试设计一个算法, 计算出从三角形的顶至底的一条路径, 使该路径经过的数字和最大. 算法设计: 对于给定的n行数字组成的三角

    2024年01月17日
    浏览(47)
  • 谭浩强【C语言程序设计】第五章习题详解

    目录 1.请画出例5.6 中给出的 3个程序段的流程图。 2.请补充例5.7程序,分别统计当“fabs(t)=1e-6”和“fabs(t)=1e-8”时执行循环体的次数。 3.输入两个正整数m 和n,求其最大公约数和最小公倍数。 4.输入一行字符,分别统计出其中英文字母、空格、数字和其他字符的个数。 5. 求S

    2024年01月23日
    浏览(55)
  • 计算机网络(谢希仁-第八版)第五章习题全解

    5-01 试说明运输层在协议栈中的地位和作用。运输层的通信和网络层的通信有什么重要的区别?为什么运输层是必不可少的? 地位和作用: 从通信和信息处理的角度看,运输层向它上面的应用层提供通信服务,它属于面向通信部分的最高层,同时也是用户功能的最低层,当网

    2024年02月09日
    浏览(53)
  • 【算法设计与分析】动态规划-练习题

    输入一个整数数组 S[n] ,计算其最长递增子序列的长度,及其最长递增子序列。 定义 k ( 1 ≤ k ≤ n ) k (1 ≤ k ≤ n) k ( 1 ≤ k ≤ n ) ,L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。 对于每一个k,我们都遍历前面0~k-1的所有的数,找出最大的L[i],且 S [ k ] L [

    2024年02月03日
    浏览(57)
  • 《python语言程序设计基础》(第二版)第五章课后习题参考答案

    第五章 函数和代码的复用 5.1 改造练习题3.5,输出更大的田字格 5.2 实现isOdd函数 5.3 实现isNum函数 5.4 实现multi函数 5.5 实现isPrime函数 5.6 输出10种生日日期格式 代码一: 代码二: 5.7 汉诺塔 注:上述代码仅供参考,若有问题可在评论区留言!

    2024年02月01日
    浏览(49)
  • 《Python 程序设计》张莉主编 第五章:程序控制结构 课后习题答案(一)

    本章主要介绍了在 Python 中对顺序结构、选择结构和循环结构的语句描述,并对列表解析和生成器表达式作简要介绍。 程序 = 算法 + 数据结构 而无论多么复杂的算法,都可以使用上述的三种基本控制中的一种或几种组成。 BTW , 这一章的作业有点长,所以打算分两次上传 (实

    2024年02月07日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包