当前位置: 首页 > news >正文

【算法】动态规划

一、基础知识

动态规划的基本思想:将待求解问题分解成若干个子问题,如果各个子问题不是独立的,不同的子问题的个数只是多项式量级,为避免大量的重复计算,用一个表记录所有已解决的子问题的答案,而在需要的时候再找出已求得的答案。
分治与动态规划算法的异同
相似之处:

  1. 都可以将大问题划分为小问题求解。
  2. 都需要重叠子问题的最优解。

不同之处:

  1. 分治算法是自上而下,递归求解,然后合并结果。动态规划是自下而上,从更小的子问题开始递推。

  2. 分治算法对每个子问题只计算一次,不会重复计算。动态规划算法会存储每个子问题的解,重复使用,避免重复计算。

  3. 分治算法不需要存储中间结果,只存储最终结果。动态规划需要创建一个表来存储各个子问题的解。

  4. 分治算法对每个子问题的解需要进行合并,而动态规划只需要简单地查表即可得到解。

  5. 分治算法的时间复杂度较高,常为O(nlogn)。动态规划能达到O(n)的时间复杂度。

    总之,分治算法采用自上而下的分解方式,只存储最终结果,要进行结果合并,效率较低。动态规划采用自下而上递推的方式,存储每个子问题的最优解,通过查表得到最终解,效率较高。

理解动态规划算法的基本要素

  1. 最优子结构性质:问题的最优解包含了其子问题的最优解。
  2. 重叠子问题性质:有些子问题被反复计算多次。

动态规划算法求解问题的步骤

  1. 找出最优解的性质,并刻画其结构特征
  2. 递归地定义最优值
  3. 以自底向上的方式计算出最优值
  4. 构造最优解

二、矩阵连乘问题

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

伪代码:

//用动态规划法求解
void MatrixChain(int *p,int n,int **m,int **s)
{for (int i = 1; i <= n; i++) m[i][i] = 0;//矩阵链长度为1for (int r = 2; r <= n; r++)   //r为矩阵链长度,从2…nfor (int i = 1; i <= n - r+1; i++) {//遍历所有长度是r的子问题。//对于每一个给定的链长r,左边界为i,右边界为jint j=i+r-1;m[i][j] = +; s[i][j] = i;//记录断开位置,即加括号的位置for (int k = i; k < j; k++){//矩阵链的分隔位置从第i个矩阵…第j-1个矩阵int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}}}
}

三、最长公共子序列问题

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

int  LCSLength(char *x,char *y,int  c[ ][N],int  b[ ][N])
{     //x和y的长度     int m=strlen(x),n=strlen(y);  int i,j;  //初始化c[][]  for (i = 0; i <= m; i++) c[i][0] = 0;  for (i = 0; i <= n; i++) c[0][i] = 0;  //计算c[][]for (i = 1; i <= m; i++)   for (j = 1; j <= n; j++){//如果两个字符相同,左上方的值加1   if (x[i-1]==y[j-1]) {    c[i][j]=c[i-1][j-1]+1; b[i][j]=1;    }   //如果不相同,取左方和上方的最大值  else if (c[i-1][j] >= c[i][j-1]) {     c[i][j]=c[i-1][j]; b[i][j]=2;  }  else { c[i][j]=c[i][j-1]; b[i][j]=3; }  }  //返回最长公共子序列长度return  c[m][n];
}
//通过b[][]回溯构造最长公共子序列 
void LCS(int i,int j,char *x,int **b)  
{   //到达边界,返回  if (i ==0 || j==0) return;     //向左上方移动 if (b[i][j]== 1){ LCS(i-1,j-1,x,b); cout<<x[i]; }     //向左方移动else if (b[i][j]== 2) LCS(i-1,j,x,b);   //向上方移动else LCS(i,j-1,x,b);  
}

四、最大子段和问题

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

int maxSum(int a[],int n,int &begin,int &end){int sum=0;   //结果,最大子序列和int b=0;     //当前和for(int i=0;i<n;i++){if(b>0) b+=a[i]; //如果b大于0,加上当前元素 else{  b=a[i];   //如果b等于0,重新开始,b赋值为当前元素值begin=i;  //记录开始位置  }if(b>sum){ //如果当前和大于结果,更新结果和结尾位置 sum=b;   end=i;  }   }return sum;   //返回结果
} 

五、0-1背包问题

在这里插入图片描述

在这里插入图片描述

int  Knapsack(int v[], int w[], int c, int n, m[][])  
{     //初始化第一行和第一列,均为0for(int i=0;i<=n;i++)  m[i][0]=0;  for(int j=0;j<=c;j++)  m[0][j]=0;  //自底向上计算每个子问题的最优值for(i=1;i<=n;i++) for(j=1;j<=c;j++){     //如果不能装下,最大价值就是不考虑该物品的价值if(j<w[i]) m[i][j]=m[i-1][j];     //如果能装下,取决于装入或不装入该物品的最大值elsem[i][j]=max(m[i-1][j], m[i-1][j-w[i]]+v[i]);}  //返回总的最大价值return m[n][c];
}

相关文章:

【算法】动态规划

一、基础知识 动态规划的基本思想&#xff1a;将待求解问题分解成若干个子问题&#xff0c;如果各个子问题不是独立的&#xff0c;不同的子问题的个数只是多项式量级&#xff0c;为避免大量的重复计算&#xff0c;用一个表记录所有已解决的子问题的答案&#xff0c;而在需要的…...

HNOI2014 世界树

洛谷P3233 [HNOI2014]世界树 题目大意 有一棵 n n n个点的树&#xff0c;每个点有一个编号&#xff0c;有 q q q次操作。对于每次操作&#xff0c;给出 m m m个点并称为议事点&#xff0c;树上各个点由离这个点最近的议事点管理&#xff08;如果有多个议事点离这个点最近&…...

在MyBatis XML文件中处理特殊符号的方法,如“>”、“<”、“>=”、“<=”这些符号XML会报错如何处理

前言 在MyBatis的XML映射文件中&#xff0c;我们经常需要使用特殊符号&#xff0c;比如"大于"、"小于"、"大于等于"、"小于等于"等比较操作符。然而&#xff0c;这些符号在XML中具有特殊的含义&#xff0c;因此需要进行特殊处理&…...

第三章--第一篇:什么是对话系统?

对话系统是一种人机交互的技术,旨在使计算机能够与人类进行自然而流畅的对话。它是人工智能领域的重要研究方向,具有重要的实际应用价值和广泛的普适性。 首先,对话系统的重要性在于它可以提供高效便捷的人机交互方式。传统的人机界面,如图形用户界面(GUI)和命令行界面(…...

项目基础搭建

一、项目创建 1.下载并安装nodejs 下载完成后&#xff0c;查看node版本 winR 快捷键&#xff0c;cmd确定&#xff0c;进入后台黑框 node -v查看npm安装路径 npm root -g安装cnpm镜像 npm install -g cnpm --registryhttps://registry.npm.taobao.org&#xff1a;查看npm版…...

PFCdocumentation_FISH Rules and Usage

目录 FISH Scripting FISH Rules and Usage Lines Data Types Reserved Names for Functions and Variables Scope of Variables Functions: Structure, Evaluation, and Calling Scheme Arithmetic: Expressions and Type Conversions Redefining FISH Functions Ex…...

如何完美卸载VS2015(2023年5月份实测有效)

使用控制面板卸载VS2015&#xff0c;出现正在配置您的系统&#xff0c;这可能需要一些时间&#xff0c;然后就出现卡住半个小时第二行的条都没有动的问题&#xff0c;这里提供vs2015以及以前版本的卸载方式 问题产生原因:他需要下载一些东西&#xff0c;然后由于你懂的网络原因…...

JavaScript如何声明和定义函数

JavaScript是一门非常有趣的编程语言&#xff0c;它可以让我们创建各种各样的函数来解决各种各样的问题。在JavaScript中&#xff0c;函数的声明和定义非常重要&#xff0c;因为它们决定了函数的行为和执行过程。 首先&#xff0c;让我们来看看JavaScript中函数的声明。在Java…...

微信小程序 WebSocket 通信 —— 在线聊天

在Node栏目就讲到了Socket通信的内容&#xff0c;使用Node实现Socke通信&#xff0c;还使用两个流行的WebSocket 库&#xff0c;ws 和 socket.io&#xff0c;在小程序中的WebSocket接口和HTML5的WebSocket基本相同&#xff0c;可以实现浏览器与服务器之间的全双工通信。那么本篇…...

VMware快照:简化虚拟化环境管理与数据保护

引言&#xff1a; 在虚拟化环境中&#xff0c;数据保护和灵活性是至关重要的。VMware快照作为一项强大的功能&#xff0c;为虚拟机管理者提供了便利和安全性。本文将介绍VMware快照的使用&#xff0c;以及它为用户带来的几个关键优势。 VMware快照是一项重要的功能&#xff0c…...

图的最短路径

最短路径算法对图结构没有特殊要求&#xff0c;不要求连通图&#xff0c;且有向图无向图均可。 最短路径算法目标是求得从某顶点出发&#xff0c;沿图的边到达另一顶点所经过的路径中&#xff0c;各边上权值之和最小的一条路径。解决最短路的问题有以下算法&#xff1a;Dijkst…...

RHCE----Shell变量和引用

1.变量的类型及含义 变量类型: 1、自定义变量: 在当前的shell命令行界面设置的变量是局部变量 例子&#xff1a; num1 namezhangsan 2、环境变量全局变量,通过export 导出后的局部变量是全局变量 、bash的初始化文件&#xff1a;/etc/profile&#xff1a;存放一些全局变量…...

【Redis】聊一下缓存雪崩、击穿、穿透、预热

缓存的引入带来了数据读取性能的提升&#xff0c;但是因此也引入新的问题&#xff0c;一个是数据双写一致性&#xff0c;另一个就是雪崩、击穿、穿透&#xff0c;那么如何解决这些问题&#xff0c;我们来说下对应的问题和解决方案 雪崩 缓存雪崩&#xff1a;同一时间内大量请…...

全景描绘云原生技术图谱,首个《云原生应用引擎技术发展白皮书》发布

5月12日&#xff0c;由神州数码主办、北京经开区国家信创园、中关村云计算产业联盟协办的2023通明湖论坛-云原生分论坛在京召开。论坛期间&#xff0c;神州数码联合北京通明湖信息技术应用创新中心、中国信通院和通明智云正式发布了《云原生应用引擎技术发展白皮书》&#xff0…...

【Python共享文件】——Python快速搭建HTTP web服务实现文件共享并公网远程访问

文章目录 1. 前言2. 视频教程3. 本地文件服务器搭建3.1 python的安装和设置3.2 cpolar的安装和注册 4. 本地文件服务器的发布4.1 Cpolar云端设置4.2 Cpolar本地设置 5. 公网访问测试6. 结语 1. 前言 数据共享作为和连接作为互联网的基础应用&#xff0c;不仅在商业和办公场景有…...

Mysql数据库分库分表

为什么使用分库分表&#xff1f; 传统的将数据集中存储至单一数据节点的解决方案&#xff0c;在性能、可用性和运维成本这三方面已经难于满足互联网的海量数据场景。 1&#xff09;性能 从性能方面来说&#xff0c;由于关系型数据库大多采用 B 树类型的索引&#xff0c;在数…...

SpringBoot热部署插件原理分析及实战演练

目录 1、关于热部署&#xff08;Hot Deploy&#xff09;产生的背景 1&#xff09;热部署出现前 2&#xff09;热部署出现后 2、spring-boot-devtools插件原理 1&#xff09;解决变更文件自动加载到JVM中 2&#xff09;spring-boot-devtools重启速度比手动重启快 3、关于…...

【C++ 入坑指南】(10)函数

文章目录 简介定义实例函数的分文件编写 简介 函数是一组一起执行一个任务的语句。每个 C 程序都至少有一个函数&#xff0c;即主函数 main() &#xff0c;所有简单的程序都可以定义其他额外的函数。 您可以把代码划分到不同的函数中。如何划分代码到不同的函数中是由您来决定…...

P2233 [HNOI2002]公交车路线

题目描述 在长沙城新建的环城公路上一共有 8 个公交站&#xff0c;分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行&#xff0c;因此你从某一个公交站到另外一个公交站往往要换几次车&#xff0c;例如从公交站 A 到公交站 D&#xff0c;你就至少需要…...

java入门-W11(K168-K182)网络编程

1. 网络编程入门 1.1 网络编程概述 计算机网络 是指将地理位置不同的具有独立功能的多台计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统&#xff0c;网络管理软件及网络通信协议的管理和协调下&#xff0c;实现资源共享和信息传递的计算机系统…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...