动态规划应用

介绍

是用来解决一类最优问题的算法思想，将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解得到。

递归写法实例

优化斐波那契数列

int F(int n){
    if(n==0||n==1) return 1;
    else{
       return F(n-1)+F(n-2);
       }

有太多重复计算，可用一个数组记录计算的结果，出现过则直接返回，无需再进行重复计算

const int maxn=100;
int dp[maxn];
int F(int n){
    if(n==0||n==1) return 1;
    if(dp[n]!=-1) return dp[n];
    else{
       dp[n]=F(n-1)+F(n-2);
       return dp[n];
       }

递推写法实例

求数塔问题
在这里插入图片描述
思路：由底往上推求和

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100;
int str[maxn][maxn],num;
int dp[maxn][maxn];

int main(){
    cin>>num;
    //输入
    for(int i=1;i<=num;i++){
        for(int j=1;j<=i;j++){
            cin>>str[i][j];
        }
    }
    //由底往上开始，初始化边界的状态
    for(int j=1;j<=num;j++){
        dp[num][j]=str[num][j];
    }
    //计算
    for(int i=num-1;i>0;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+str[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
    return 0;
}

典型例题

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100;
int str[maxn],num;
int dp[maxn];

int main(){
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>str[i];
    }
    //求和
    dp[0]=str[0];//从0开始记录最大和
    for(int i=1;i<num;i++){
        //当i-1之前的结点为负数时，最大值为本身，否则求和最大
        dp[i]=max(str[i],dp[i-1]+str[i]);
    }
    //求下标
    int k=0;
    for(int j=1;j<num;j++){//无需遍历0下标
        if(dp[k]<dp[j])
        k=j;
    }
    cout<<dp[k]<<endl;
    return 0;
}

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100;
int str[maxn],num;
int dp[maxn];

int main(){
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>str[i];
    }
    int k=-1;//找最长子序列
    for(int i=0;i<num;i++){
        dp[i]=1;//先初始化为最短状态：即本身一个序列
        for(int j=0;j<i;j++){
            //i>j,首先是递增，正常最小：dp[i]=dp[j]+1,说明后一个小于前一个
            if(str[i]>=str[j]&&dp[j]+1>dp[i])
            dp[i]=dp[j]+1;
        }
    k=max(k,dp[i]);
    }
    cout<<k<<endl;
    return 0;
}

砝码称重

思路：
记：左-负 右-正 不选-0
计算总质量-w[i]
利用递推去实现：定义一个动态数组dp[i][j]-表示从前i个物品中选重量为j的砝码，
则i:由1-N；j:由0-总重量 dp=记录种类数
不同情况：1.不选:dp[i][j]=f[i-1][j]-重量不变
2.放左边 :dp[i][j]=f[i-1][j-w[i]]-放左边重量-：对负数处理-abs(负权)
3.放右边：dp[i][j]=f[i-1][j+w[i]]-放右边重量+
则其转移方程：dp[i][j]=f[i-1][j+w[i]]||dp[i][j]=f[i-1][j-w[i]]||dp[i][j]=f[i-1][j]
在这里插入图片描述

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

const int maxn=110;
int n,num=0,w[maxn],dp[maxn][1e5];


int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  int m=0;
  //输入求和
  for(int i=1;i<=n;++i) {
    cin>>a[i];
    m+=a[i];
  }
  //启示录
  f[0][0]=1;//重量为0的砝码，记录
  //
  for(int i=1;i<=n;++i)//个数
  for(int j=m;j>=0;--j)//j:总重量->0变化
  f[i][j]=f[i-1][j]||f[i-1][abs(j-a[i])]||f[i-1][j+a[i]];
  int ans=0;
  for(int i=1;i<=m;++i)//遍历不同质量的砝码，统计种类
  if(f[n][i]) ans++;
  cout<<ans<<endl;
  return 0;
}

接龙序列

在这里插入图片描述

//先声明这不是我写的，这是大佬的代码！！！！！
//因为我差不多花了1小时才理解，尊滴很无助，所以想分享一下自己的理解，让大家能有点借鉴吧，
#include <iostream>
#include <bits/stdc++.h>
#include <string>
using namespace std;
const int maxn=10;
int n,dp[maxn];
int t,h,m=0;
string s;
//求最少删除的个数——>求最长的接龙序列长度——>用动态数组记录最大数m——>用总数-m为所求值
//其中动态数组：下标记录字符，值记录出现次数
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
    cin>>s;
    h=s[0]-'0';
    t=s[s.length()-1]-'0';
    dp[t]=max(dp[h]+1,dp[t]);//可实现首尾字符出现次数++，因为dp[h]+1,而dp[t]=dp[h]+1,相当于次数++;记录两者最大值可得最长接龙长度
    m=max(m,dp[t]);//记录下来
  }
  cout<<n-m<<endl;
  return 0;
}

叠硬币

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100;
int num,cou=0;
int n,m;
int dp[maxn];

int re(){
  dp[0]=dp[1]=1;
  for(int i=2;i<=n;i++){
    dp[i]=dp[i-1]+dp[i-2];
    if(dp[i]%m==0)
    cou++;
  }
  return cou;
}
int main()
{
  memset(dp,0,sizeof(dp));
  cin>>num;
  // for(int i=0;i<num;i++){
    cin>>n>>m;
    cout<<re();
  // }
  // 请在此输入您的代码
  return 0;
}

2022

在这里插入图片描述

#include <iostream>
using namespace std;

int main()
{
  // 2022->10个不同的
  2022=2*1000+20+2=1011*2
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
long long pd[2022+1][10+1]{1};
int main() {
    for (int i = 1; i <= 2022; i++)
        for (int j = 1; j <= 10; j++)
            if (i >= j) pd[i][j] = pd[i - j][j] + pd[i - j][j - 1];
    cout<<pd[2022][10];
}

最小权值

在这里插入图片描述

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

typedef long long ll;
ll num[2030];

int main()
{
  // ios::sycn_with_stdio(0);
  // cin.tie(0);cout.tie(0);
  memset(num,127,sizeof(num));
  num[0]=0;
  for(int i=1;i<=2021;++i){
    for(int j=0;j<i;++j){
      num[i]=min(num[i],1+2*num[j]+3*num[i-j-1]+j*j*(i-j-1));
    }
  }
  cout<<num[2021];
  // 请在此输入您的代码
  return 0;
}

小蓝与钥匙

在这里插入图片描述

#include <iostream>
using namespace std;

typedef long long ll;

ll f[2030];

ll c(int n,int m){
  ll res=1;
  for(int i=1;i<=m;++i){
    res=res*(n-i+1)/i;
  }
  return res;
}

int main()
{
  f[1]=0,f[2]=1;
  for(int i=3;i<=14;++i){
    f[i]=(i-1)*(f[i-1]+f[i-2]);
  }
  cout<<c(28,14)*f[14];
  return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

oracle数据库怎么查看当前登录的用户？

oracle数据库怎么查看当前登录的用户？

方法如下&#xff1a; 输入select * from dba_users; 即可。 常用语句&#xff1a; 一&#xff0c;查看数据库里面所有用户&#xff1a; select * from dba_users; 前提是你是有dba权限的帐号&#xff0c;如sys,system。 二&#xff0c;查看你能管理的所有用户&#xff1…
阅读更多...
.[[backup@waifu.club]].svh勒索病毒数据怎么处理|数据解密恢复

.[[backup@waifu.club]].svh勒索病毒数据怎么处理|数据解密恢复

尊敬的读者&#xff1a; 近年来&#xff0c;随着信息技术的迅猛发展&#xff0c;网络安全问题日益凸显&#xff0c;其中勒索病毒成为了一大威胁。.[[backupwaifu.club]].svh、.[[MyFilewaifu.club]].svh勒索病毒就是其中之一&#xff0c;它以其独特的传播方式和恶劣的加密手段…
阅读更多...
Spring AMQP消息中间件

Spring AMQP消息中间件

SpringAMQP简单说就是一个中间件&#xff0c;提供了模板方便我们操作各种消息模型 上面已经学了RabbitMQ消息队列是有五种消息模型&#xff0c;并且我们演示了其中的基本消息队列(Hello World)。用的是官方API&#xff0c;来实现的基本消息队列(Hello World)。会发现官方提供的…
阅读更多...
华为OD-C卷-攀登者1[100分]

华为OD-C卷-攀登者1[100分]

攀登者喜欢寻找各种地图，并且尝试攀登到最高的山峰。 地图表示为一维数组，数组的索引代表水平位置，数组的元素代表相对海拔高度。其中数组元素0代表地面。 例如： [0,1,2,4,3,1,0,0,1,2,3,1,2,1,0]，代表如下图所示的地图 地图中有两个山脉位置分别为 1,2,3,4,5 和 8,9,1…
阅读更多...
一、OpenCvSharp环境搭建

一、OpenCvSharp环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…
阅读更多...
K8S哲学 - 常见的资源类型

K8S哲学 - 常见的资源类型

资源类型 namespace kubectl apply 和 kubectl create kubectl apply是声明式的 和 kubectl create是命令式的对吗 deployment 和 job的区别
阅读更多...
Fiddle配置代理，保手机模拟器访问外部网络

Fiddle配置代理，保手机模拟器访问外部网络

前言&#xff1a; 嘿&#xff01;大家好&#xff01;我来带你们玩转Fiddler和Mumu模拟器的组合技了&#xff01;此组合技能帮助你实现在模拟器上畅游外部网络。相信我&#xff0c;它会让你的开发和测试过程更加轻松愉快&#xff01;废话不多说&#xff0c;赶紧展开我们的冒险吧…
阅读更多...
bugku-web-file_get_contents

bugku-web-file_get_contents

<?php extract($_GET); if (!empty($ac)){$f trim(file_get_contents($fn));if ($ac $f){echo "<p>This is flag:" ." $flag</p>";}else{echo "<p>sorry!</p>";} } ?> 这里涉及到几个不常用的函数 这里直接构…
阅读更多...
22.04 忘记root密码

22.04 忘记root密码

在即将加载Ubuntu启动界面时&#xff0c;在 GRUB 引导菜单出现之前马上按住 Shift 键&#xff0c;将进入引导菜单 在引导菜单中选择 “Advanced options for Ubuntu”&#xff0c;如果是中文则显示为“Ubuntu高级选项” 接下来你会看到好几个内核版本号&#xff0c;按上下键选…
阅读更多...
区块链安全-----接口测试-Postman

区块链安全-----接口测试-Postman

Postman是一款支持http协议的接口调试与测试工具&#xff0c;其主要特点就是功能强大&#xff0c;使用简单且易 用性好 。无论是开发人员进行接口调试&#xff0c;还是测试人员做接口测试&#xff0c;Postman都是我们的首选工具 之一 。 更早的接入测试&#xff0c;更早的发现问…
阅读更多...
数据结构与算法

数据结构与算法

根据希赛相关视频课程汇总整理而成&#xff0c;个人笔记&#xff0c;仅供参考。 数据结构 包括逻辑结构和物理结构 线性表 一对一的关系 栈/队列&#xff1a;操作受限的线性表 串&#xff1a;由零个或多个任意字符组成的有限序列 S“a1, a2, …, an” (n≥0) 串长度&#…
阅读更多...
69787987

69787987

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…
阅读更多...
实现智能水控 | 基于ACM32 MCU的分体式水控方案

实现智能水控 | 基于ACM32 MCU的分体式水控方案

分体式水控概述 分体式水控是一种常见的水控系统&#xff0c;它的工作原理是通过水的流动来控制水的供应和排放&#xff0c;该系统一般由两部分组成&#xff1a;控制器和水阀。控制器负责监测水的流量和压力&#xff0c;根据设定的参数来控制水阀的开和关&#xff0c;从而实现水…
阅读更多...
何谓电子邮件加密？探讨其工作原理及多种加密形式的运用

何谓电子邮件加密？探讨其工作原理及多种加密形式的运用

在现今信息化社会&#xff0c;电子邮件已经成为日常生活与商务活动中无可替代的通讯手段&#xff0c;每日全球往来邮件的数量高达数十亿封&#xff0c;这些邮件中往往包含了个人隐私信息、账户密码、金融交易详情、法律文件、专利技术等内容&#xff0c;一旦落入网络不法分子之…
阅读更多...
Amazon Bedrock 实践系列 | Claude 3 深度探秘

Amazon Bedrock 实践系列 | Claude 3 深度探秘

生成式 AI 和大模型在 2024 年已经进入落地实践阶段。因此&#xff0c;围绕开发者在生成式应用程序开发中的主要痛点和需求&#xff0c;我们组织了这个 “Amazon Bedrock 实践” 的系列&#xff0c;希望可以帮助开发者高效地上手生成式 AI 和大模型的应用开发。本篇为第二篇&am…
阅读更多...
JavaWeb-Ajax

JavaWeb-Ajax

文章目录 1.基本介绍2.应用场景3.两种通信方式对比1.传统web通信方式2.Ajax通信方式 4.原生Ajax1.快速入门1.案例2.创建maven项目&#xff0c;导入依赖3.编写代码1.User.java2.login.html3.CheckUserServlet.java4.结果 4.后置资料5.课后作业——接入DB1.导入依赖2.创建德鲁伊连…
阅读更多...
一些优雅的算法（c++）

一些优雅的算法（c++）

求最大公约数&#xff1a;辗转相除法 int gcd(int a,int b){return b0?a:gcd(b,a%b); }求最小公倍数&#xff1a;两整数之积除以最大公约数 int lcm(int a, int b){return a*b / gcd(a, b); }十进制转n进制&#xff1a; char get(int x){if(x<9){return x0;}else{return…
阅读更多...
【Mybatis-Plus】Mybatis-Plus增删改查示例

【Mybatis-Plus】Mybatis-Plus增删改查示例

示例一&#xff1a;delete 这个删除&#xff0c;是我们直接可以把这条记录给放进去&#xff0c;那么这条记录里面如果说有的属性为空的话&#xff0c;它是不会去管的&#xff0c;但是有些属性它不为空的话&#xff0c;那么它就会根据属性。作为一个equal的条件去做一个删除的一…
阅读更多...
Android性能优化RecyclerView预加载LayoutManager的getExtraLayoutSpace，Kotlin

Android性能优化RecyclerView预加载LayoutManager的getExtraLayoutSpace，Kotlin

Android性能优化RecyclerView预加载LayoutManager的getExtraLayoutSpace&#xff0c;Kotlin RecyclerView默认只加载当前屏幕肉眼可见区域的有限item数量&#xff0c;有些场景下&#xff0c;需要在屏幕外不可见的区域多加载一批item出来&#xff0c;这有时候被称之为“预加载”…
阅读更多...
Docker Desktop修改镜像存储路径 Docker Desktop Start ... 卡死

Docker Desktop修改镜像存储路径 Docker Desktop Start ... 卡死

1、CMD执行wsl -l -v --all 2、Clean / Purge data 3、导出wsl子系统镜像: wsl --export docker-desktop D:\docker\wsl\distro\docker-desktop.tar wsl --export docker-desktop-data D:\docker\wsl\data\docker-desktop-data.tar4、删除现有的wsl子系统&#xff1a; wsl -…
阅读更多...
最新文章

Copyright @ 2022~2023