(蓝桥杯C/C++)——动态规划(DP)

目录

一、线性DP

1.DP(动态规划)简介

2.动态规划的分析步骤

3.例题讲解

二、二维DP

1.二维DP简介

2.选数异或

三、最长上升子序列LIS

1.LIS简介

2.例题讲解

四、最长公共子序列LCS

1.最长公共子序列

2.最长公共子序列

2.求出具体子序列


一、线性DP

1.DP(动态规划)简介

DP(动态规划)全称DynamicProgramming,是运筹学的一个分支,是一种将复杂问题分解成很多重叠的子问题,并通过子问题的解得到整个问题的解的算法。

在动态规划中有一些概念:
状态:就是形如dp[il[il=val的取值,其中i,i为下标,也是用于描述、确定状态所需的变量,val为状态值。
状态转移:状态与状态之间的转移关系,一般可以表示为一个数学表达式,转移方向决迭代或递归方向。
最终状态:也就是题目所求的状态,最后的答案。

2.动态规划的分析步骤

1.确定状态,一般为“到第i个为止,xx为j(xx为k)的方案数/最小代价/最大价值”,可以根据数据范围和复杂度来推理。

2.确定状态转移方程,即从已知状态得到新状态的方法,并确保按照这个方向一定可以正确躾渥黨瘛得到最终状态。
根据状态转移的方向来决定使用迭代法还是递归法(记忆化)

3.确定最终状态并输出。

3.例题讲解

破损的楼梯
问题描述
小孟来到了一座高耸的楼梯前,楼梯共有N级台阶,从第0级台阶出发。小孟每次可以迈上1级或2级台阶,但是,楼梯上的a级、第02级、第 a1级,以此奔推。共 M 级台阶的台阶面已经坏了,不能上去。
现在,小孟想要到达楼梯的顶端,也就是第N级台阶,但他不能踩到坏了的台阶上。请问有多少种不踩到坏了的台阶上到达顶端的方案数?
由于方案数很大,请输出其对1e9+7取模的结果

例题分析

设状态dp[i]表示走到第i级台阶的方案数。
状态转移方程为dp[i]=dp[i-1]+dp[i-2],如
果i为破损的,则dp[il=0。
可以用一个桶来记录哪些位置是破损的。
从前往后更新,最后输出dp[n]。

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

const int N = 1e5+10,mod - 1e9+7;

int n,m,x,f[N],vis[N];

signed main()

{

     cin >> n >> m;

     for(int i=l;i<=m;i ++)

      {

        cin >> x;

        vis[x]= 1;

}
f[0]= 1;

for(int i - 1;i < -n; i++)

     {

        if(vis[i])

         continue;

         fi]-f[i -1+f[i - 2];

         f[i] %= mod;

  }
cout << f[n] << '\n';

return 0;

}

二、二维DP

1.二维DP简介

二维DP就是指dp数组的维度为二维的dp(当然有时候可能会三维四维,或者存在一些优化使得它降维成一维),广义的来讲就是有多个维度的dp,即用于描述dp状态的变量不止一个。

2.选数异或

给定n个正整数a[i],询问你其中有多少个不同子序列进行异或运算的值为x?
由于结果很大,你需要对998244353取模

异或运算:位远算的一种,符号为由,1^1=0,1^0=1,0^0=0.

子序列: 从切始序列中选出若于个数保持原有顺序的序列,

例题分析

设状态dp[i][j]表示到第i个数字为止(但不一定以第i个数字结尾),异或和为i的子序列个数。

对于第i层的状态,转移的方式有“选第i个”和“不选第i个”两种,转移方程为dp[i][j]= dp[i][j] + dp[i - 1]j ^ dp[i-1[j ^ a]]。
最后结果就是dp[n][x]。

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

using ll = long long;

const int N = 1e5+9;

const ll p = 998244353;

int a[N],dp[N][70];


int main()

{
    int n, x; cin >> n >> x;

   dp [0] [0 = 1;

   for(int i = 1; i <= n; ++ i)

    {

      for(int j = 0; j < 64; ++j)

       {
         dp[i][j] = (dp[i-1][j] + dp[i-1][j ^ a[i]]) % p;

        }

     }
cout << dp[n][m] << '\n';

return 0;

}

三、最长上升子序列LIS

1.LIS简介

LIS(最长上升子序列)是一个经典的DP模型。
子序列指的是一个序列中,按照原顺序选出若干个不一定连续的元素所组成的序列。这节课我们讲解O(n^2)时间复杂度的朴素LIS模型,LIS还有一种利用二分实现的O(nlogn)时间复杂度的模型,大家可以自行去学习,理解起来略有难度。在求解LIS时,一般我们会设dp[i]表示1~i序列中以a[i]结尾的最长上升子序列的长度,状态转移方程为:
dp[i]= max(dp[j] + 1),

if a[i]> a[j]
表示a[i]要插入到不同子序列后面的情况。

a13425372
dp12324352

2.例题讲解

小明是蓝桥王国的勇士,他晋升为蓝桥骑士,于是决定不断突破自我
这天蓝桥首席骑士长给他安排了 N 个对手,他们的战力值分别为….a1,a2,···an,且按顺序挡在小明的前方,对于这些对手小明可以选择单挑也可以选择群战
作为热血豪放的勇士,小明从不走回头路,且只愿意挑战战力值越来越强的对手
请你算算小明最多会挑战多少名对手

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

const int N = 1e3+9;

int a[N],dp[N];

int main()

{

  int n;

  cin >> n;

 for(int i = 1;i <= n; ++i)

 cin >> a[i];

    for(int i = 1;i <= n; ++i)

    {

        dp[i] = 1;

         for(int j =1;j < i; ++j)

         {

           if(a[i] > a[j])

            dp[i] = max(dp[i], dp[j] + 1);

          }

    }

   int ans = 0;

   for (int i =1;i < n; ++i)

    ans = max(ans, dp[i]);

    cout << ans << '\n';

   return 0;

}

四、最长公共子序列LCS

1.最长公共子序列

LCS(Longest Common Subsequence 最长公共子序列)是一个经典的DP模型。
这节课我们讲解O(n^2)时间复杂度的LCS模型。
LCS问题是给定两个序列A和B,求它们的最长公共子序列。

在求解LCS时,一般我们会设dp[i][j]表示A[1~i]序列和B[1~j]序列中(不规定结尾)的最长公共子序列的长度,状态转移方程为:
if ali]=b[j]:dp{i][j]= dp{i-1][j-1]+1
else dp[i][j]= max(dp[i-1][jl, dp[i][j-1]);

解释一下:当ali]=b[j]时,可以将他们作为插入到LCS的后面,使得长度变长1,当a[i]!=b[说明此时LCS不会延长,那就要从dp[i-1][j]和dp[i][j-1]中取大的作为最长的长度。

a13425
b14352

dp12345
11111
211222
312222
412223
512233

132

2.最长公共子序列

给定一个长度为 N 数组 a 和一个长度为 M 的数组 b

请你求出它们的最长公共子序列长度为多少。

例题分析

设dp[i][j]表示序列a[1~i],b[1~j]中最长公共子序列长度,

状态转移方程为:

if ali]=b[j]:dp[i][j] = dp[i-1][j-1]+1
else: dp|i][j]= max(dp[i-1][j], dp[i][j-1]);最后输出dpln]lm]即可。

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

const int N = 1e3+9,

int n, m,a[N], b[N], dp[M][N];

int main()

{

    int n, m;

    cin >> n >> m;

    for(int i = 1;i <= n; ++i)

    cin >> a[i];
    for(int i= 1; j<= m; ++i)

    cin >> b[i];

   for(int i = 1;i <= n; ++i)

      for(int j = 1; j <= n; ++j)

      {

              if(a[i] == b[j])

                      dp[i][j] = dp[i - 1][j - 1] + 1;

               else dp[i][j] = max(dp[i - 1][j],dp[i ][j - 1]);

        }

   cout << dp[n][m] << '\n';

   return 0;

   

2.求出具体子序列

a13425
b14352

dp12345
11111
211222
312222
412223
512233

132

(i,j)从(n,m)往回走,当a[i]=b[j]时,往左上角走变为(i-1,j-1),此时找到了一个公共元素a[i](或blj]),否则往左边或上边走(选择较大的方向)。

走到新位置后重复以上判断,直到走出边界

#include <bits/stdc+.h>
using namespace std;
using ll = long long;
const ll p= 1e9 + 7;
const int int = 1e9, N = 1e3 + 9;
int a[N], b[N], dp[N][N];
int main()

{
     int n, m;

     cin >> n >>m;

     for(int i = 1; i <= n; ++i)

     cin >> a[i];

      for(int i = 1; i <= m; ++i)

    cin >> b[i];

     for(int i = 1; i <= n; ++i)

     {
          for(int j= 1; j<= m; ++ j)

           {

             if(a[i] == b[j])

              dp[i][j] = dp[i - 1][j - 1] + 1;

              else dp[i][j] = max(dp[i][j-1],dp[i - 1][j]);

              }

    }

   vector<int> v;

   int x = n, y = n;

   while(x && y)

   {

       if(a[x] == b[y])

        {

            v.push_back(a[x]);

             x --, y--;

         }

          else (dp[x - 1][y] > dp[x][y - 1])

        x --;

         else y--;

  }

reverse(v.begin(),v.end());

 for(const auto &i : v)

 cout << i << ' ';

 return 0;

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/468967.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于Matlab 疲劳驾驶检测

Matlab 疲劳驾驶检测 课题介绍 该课题为基于眼部和嘴部的疲劳驾驶检测。带有一个人机交互界面GUI&#xff0c;通过输入视频&#xff0c;分帧&#xff0c;定位眼睛和嘴巴&#xff0c;通过眼睛和嘴巴的张合度&#xff0c;来判别是否疲劳。 二、操作步骤 第一步&#xff1a;最…

11.11 代码块

一 java 1.代码块 1&#xff09; 理解 使用构造器时&#xff1a;先默认 调用代码块内容 再调用 构造器内容【代码块 > 构造器】 1.1 细节 1&#xff09;静态代码块 只能加载一次 2&#xff09;先调用父类代码块 再子类代码块 3&#xff09;静态代码块是随着类加载而执行…

在gitlab,把新分支替换成master分支

1、备份master分支&#xff0c;可以打tag 2、删除master分支 正常情况下&#xff0c;master分支不允许删除&#xff0c;需要做两个操作才能删除 a、变更项目默认分支为非master分支&#xff0c;可以先随便选择 b、取消master为非保护分支 操作了上述两步&#xff0c;就可以删…

在使用element中的抽屉<el-drawer>页签<el-tabs/>组合时,echarts图表宽度显示异常问题

类似这种情况&#xff0c;宽度异常 原因&#xff1a;在展示出抽屉时&#xff0c;图表的组件一件初始化了&#xff0c;导致他的宽度提前设定好了&#xff08;我默认的style"width: 100%; height: 300px;"&#xff09;&#xff0c;我得解决方法有2个&#xff1a; 1、第…

《大模型应用开发极简入门》笔记

推荐序 可略过不看。 初识GPT-4和ChatGPT LLM概述 NLP的目标是让计算机能够处理自然语言文本&#xff0c;涉及诸多任务&#xff1a; 文本分类&#xff1a;将输入文本归为预定义的类别。自动翻译&#xff1a;将文本从一种语言自动翻译成另一种语言&#xff0c;包括程序语言。…

Unicode字符集(万国码)

1.三种编码方式&#xff1a; UTF-16&#xff1a;16个bit位&#xff08;2个字节&#xff09;存储 UTF-32&#xff1a;32个bit位&#xff08;4个字节&#xff09;存储 UTF-8&#xff1a;可变长度字符编码。1-4个字节存储&#xff0c;只需记住&#xff1a;英文字母1个字节表示&…

支持 Win10 的网络环境模拟(丢包,延迟,带宽)

升级 Windows 10 以后&#xff0c;原来各种网络模拟软件都挂掉了&#xff0c;目前能用的就是只有 clumsy&#xff1a; 唯一问题是不支持模拟带宽&#xff0c;那么平时要模拟一些糟糕的网络情况的话&#xff0c;是不太方便的&#xff0c;而开虚拟机用 Linux tc 或者设置个远程 l…

【Homework】【5】Learning resources for DQ Robotics in MATLAB

Lesson 5 代码-TwoDofPlanarRobot.m 表示一个 2 自由度平面机器人。该类包含构造函数、计算正向运动学模型的函数、计算平移雅可比矩阵的函数&#xff0c;以及在二维空间中绘制机器人的函数。 classdef TwoDofPlanarRobot%TwoDofPlanarRobot - 表示一个 2 自由度平面机器人类…

在模方置平建筑失败的原因是什么?

在模方置平建筑失败的原因是什么&#xff1f; 可能是obj拓扑不连续&#xff0c;可以在网格大师使用osgb转obj功能&#xff0c;选择拓扑或者重建。 网格大师是一款能够解决实景三维模型空间参考、原点、瓦块大小不统一&#xff0c;重叠区域处理问题的工具“百宝箱”&#xff0c…

【大咖云集 | IEEE计算智能学会广州分会支持】第四届信息技术与当代体育国际学术会议(TCS 2024,12月13-15日)

第四届信息技术与当代体育国际学术会议&#xff08;TCS 2024&#xff09; 2024 4th International Conference on Information Technology and Contemporary Sports 重要信息 会议官网&#xff1a;www.icitcs.net&#xff08;会议关键词&#xff1a;TCS 2024&#xff09; 202…

常用机器人算法原理介绍

一、引言 随着科技的不断发展&#xff0c;机器人技术在各个领域得到了广泛应用。机器人算法是机器人实现各种功能的核心&#xff0c;它决定了机器人的行为和性能。本文将介绍几种常用的机器人算法原理&#xff0c;包括路径规划算法、定位算法和运动控制算法。 二、路径规划算法…

Cynet:全方位一体化安全防护工具

前言 1999年&#xff0c;布鲁斯施奈尔曾说过&#xff1a;“复杂性是安全最大的敌人。”彼时还是19年前&#xff0c;而现在&#xff0c;网络安全已然变得更加繁杂。 近日我在网上冲浪过程中发现了这么一个平台性质的软件&#xff0c;看似具有相当强的防护能力。 根据Cynet的描…

dolphin 配置data 从文件导入hive 实践(一)

datax 支持多种数据源的相互读写&#xff0c;作为开源软件&#xff0c;提供了离线采集功能&#xff0c;方便系统开发&#xff0c;过程中遇到诸多配置&#xff0c;需要开发者自己探索&#xff0c;免费同样有成本 配置模板 {"setting": {},"job": {"s…

Redis如何保证数据不丢失(可靠性)

本文主要以学习为主&#xff0c;详细参考&#xff1a;微信公众平台 Redis 保证数据不丢失的主要手段有两个&#xff1a; 持久化 多机部署 我们分别来看它们两的具体实现细节。 1.Redis 持久化 持久化是指将数据从内存中存储到持久化存储介质中&#xff08;如硬盘&#xf…

Linux数据管理初探

Linux数据管理初探 导语内存管理内存分配内存错用和处理 文件锁定锁文件/区域锁读写和竞争锁命令和死锁 dbm数据库例程dbm访问函数其他dbm函数 总结参考文献 导语 Linux为应用程序提供简洁的视图用来反映可直接寻址的内存空间&#xff08;但实际上可能是内存外存&#xff09;&…

Python中4个高效小技巧

分享 4 个省时的 Python 技巧&#xff0c;可以节省 10~20% 的 Python 执行时间。 包含编程资料、学习路线图、源代码、软件安装包等&#xff01;【[点击这里]】&#xff01; 反转列表 Python 中通常有两种反转列表的方法&#xff1a;切片或 reverse() 函数调用。这两种方法都…

【黑马Redis原理篇】Redis数据结构

视频来源&#xff1a;原理篇[2,15] 文章目录 1.动态字符串SDS1.1 内部结构&#xff1a; 2.IntSet3.Dict3.1 dict的内部结构3.2 dict的扩容 4.ziplist压缩列表5.QuickList6.SkipList跳表7.RedisObject对象8.Redis的五种数据结构8.1 String8.2 List8.3 Set8.4 Zset 有序集合8.5 …

WPF之iconfont(字体图标)使用

1&#xff0c;前文&#xff1a; WPF的Xaml是与前端的Html有着高度相似性的标记语言&#xff0c;所以Xaml也可同Html一般轻松使用阿里提供的海量字体图标&#xff0c;从而有效的减少开发工作度。 2&#xff0c;下载字体图标&#xff1a; 登录阿里图标库网iconfont-阿里巴巴矢量…

内网部署web项目,外网访问不了?只有局域网能访问!怎样解决?

相关技术 要实现“内网部署&#xff0c;外网访问”&#xff0c;可以使用内网穿透、VPN技术、DMZ主机、端口映射等方法。以下是对这些方法的详细解释&#xff1a; 一、内网穿透 内网穿透是一种技术&#xff0c;它通过将内网设备映射到公网上的方式&#xff0c;实现外网访问内…

Android MVVM demo(使用DataBinding,LiveData,Fresco,RecyclerView,Room,ViewModel 完成)

使用DataBinding&#xff0c;LiveData&#xff0c;Fresco&#xff0c;RecyclerView&#xff0c;Room&#xff0c;ViewModel 完成 玩Android 开放API-玩Android - wanandroid.com 接口使用的是下面的两个&#xff1a; https://www.wanandroid.com/banner/jsonhttps://www.wan…