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

【数据结构】动态规划(Dynamic Programming)

一.动态规划(DP)的定义:

求解决策过程(decision process)最优化的数学方法。

将多阶段决策过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。

二.动态规划的基本思想:

与分治法类似,将待求解问题分解成若干个子问题

但是经分解得到的子问题往往不是相互独立的。

如果使用分治法求解问题,有些子问题被重复计算了多次。

而“如何减少子问题的重复计算”是动态规划算法的关键思想。

问题:如何减少子问题的重复计算呢?

解决方案:保存已解决的子问题的答案,在需要的时候找出已经求得的答案。

三.动态规划的基本步骤

1.找出最优解的性质,并刻划其结构特征。即:寻找最优解的子问题结构。

2.递归地定义最优解。即:根据子问题的结构建立问题的递归解式,求解最优值。

3.以自底向上的方式计算出最优值。

4.根据计算最优值时得到的信息,构造最优解。

四.例题分析——多个矩阵连乘模块设计

问题描述:

实现多个矩阵连乘功能

关键问题计算:

给定n个矩阵{$A_1,A_2,......,A_n$},其中$A_i$$A_{i+1}$是可乘的,考察这n个矩阵的连乘积

$A_1A_2A_3...A_n$

由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定,也就是说该矩阵已完全加括号,则可以依此次序反复调用3个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积:

设有四个矩阵 A,B,C,D 维数分别为:

50*10;10*40;40*30;30*5

则总共有五种完全加括号的方式:

1)

(A((BC)D))

2)

(A(B(CD)))

3)

((AB)(CD))

4)

(((AB)C)D)

5)

((A(BC))D)

对于两个矩阵A(p*q)*B(q*r)(标准乘法计算):

void matrixMultiply(int *a,int *b,int *c,int ra,int ca,int rb,int cb){if(ca!=rb){cout<<"矩阵不可乘!"<<endl;}else{int i,j,k,n,sum=0;for(i=0;i<ra;i++){for(j=0;j<cb;j++){for(k=0;k<ca;k++){sum+=a[i*ca+k]*b[k*cb+j];}c[i*ra+j]=sum;sum=0;}}}
}

需要进行p*q*r次乘法计算!

矩阵连乘问题转化为:

确定矩阵连乘的计算次序,使得按照该次序计算矩阵连乘需要的数乘次数最少。

1.穷举法求解思路:

        列举出所有可能的计算次序,并计算出每一种次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。

算法复杂度分析:

对于n个矩阵的连乘积,设其不同的计算次序为P(n)

由于每种加括号方式都可以分解为两个子矩阵的加括号的问题

2.动态规划求解:

最优解结构分析:

将矩阵连乘积$A_iA_{i+1}...A_j$简记为:A[i:j],这里i<=j。

设这个计算次序在$A_k$A_{k+1}之间将矩阵断开,i<=k<j,则其相应的完全加括号的方式为:

$A_iA_{i+1}...A_k$)($A_{k+1}...A_j$)

总计算量=A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量。

特征:计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

最优子结构性质:最优解包含其子问题的最优解。

建立递归关系:(m[i,j]表示最小连乘次数)

当i=j时,A[i:j]=$A_i$,m[i,j]=0

当i<j时,m[i,j]=$min_k${m[i,k]+m[k+1,j]+$p_{i-1}p_kp_j$}

则有:

(k的位置只有j-i种可能) 

注:由于矩阵乘法中$A_i$的列数和$A_{i+1}$的行数相等,则可以只用列数来化简表达式,这里的$p_{i-1},p_k,p_j$均表示第i-1,k,j个矩阵的列数。n个矩阵的信息,只需要一个长度为n+1的数组来表示即可。

对于m[i][j]数组,只需要填入上三角中的元素即可(因为i<=j)。

五.代码实现

#include <iostream>
using namespace std;
int BestValue(int row[],int col[], int n);
int main(int argc, const char * argv[]) {int row[]={3,4,6};int col[]={4,6,11};cout<<BestValue(row, col, 3);return 0;
}
int BestValue(int row[],int col[], int n){if(n<=0){cout<<"error";return 0;}int m[40][40];int i,j,k,r,sum;for(i=0;i<n-1;i++){if(col[i]!=row[i+1]){cout<<"error"<<endl;return 0;}}for(i=0;i<n;i++){m[i][i]=0;}for(r=1;r<n;r++){for(j=r;j<n;j++){i=j-r;sum=m[i][i]+m[i+1][j]+row[i]*col[i]*col[j];for(k=i;k<j;k++){if(sum>m[i][k]+m[k+1][j]+row[i]*col[k]*col[j]){sum=m[i][k]+m[k+1][j]+row[i]*col[k]*col[j];}}m[i][j]=sum;}}return m[0][n-1];
}

相关文章:

【数据结构】动态规划(Dynamic Programming)

一.动态规划&#xff08;DP&#xff09;的定义&#xff1a; 求解决策过程&#xff08;decision process&#xff09;最优化的数学方法。 将多阶段决策过程转化为一系列单阶段问题&#xff0c;利用各阶段之间的关系&#xff0c;逐个求解。 二.动态规划的基本思想&#xff1a; …...

Redis key过期删除机制实现分析

文章目录 前言Redis key过期淘汰机制惰性删除机制定时扫描删除机制 前言 当我们创建Redis key时&#xff0c;可以通过expire命令指定key的过期时间(TTL)&#xff0c;当超过指定的TTL时间后&#xff0c;key将会失效。 那么当key失效后&#xff0c;Redis会立刻将其删除么&#…...

ElasticSearch 谈谈分词与倒排索引的原理

ElasticSearch是一个基于Lucene的搜索服务器。Lucene是Java的一个全文检索工具包&#xff0c;而ElasticSearch则是一个分布式搜索和分析引擎。下面&#xff0c;我们将详细讨论ElasticSearch中的分词和倒排索引的原理。 分词&#xff1a; 在ElasticSearch中&#xff0c;分词是…...

【Java】Java8重要特性——Lambda函数式编程以及Stream流对集合数据的操作

【Java】Java8重要特性——Lambda函数式编程以及Stream流对集合数据的操作 前言Lambda函数式编程Stream流对集合数据操作&#xff08;一&#xff09;创建Stream流&#xff08;二&#xff09;中间操作之filter&#xff08;三&#xff09;中间操作之map&#xff08;四&#xff09…...

大话数据结构-查找-散列表查找(哈希表)

注&#xff1a;本文同步发布于稀土掘金。 8 散列表查找&#xff08;哈希表&#xff09; 8.1 定义 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f&#xff0c;使得每个关键字key对应一个存储位置f(key)。查找时&#xff0c;根据这个确定的对应关系找到给…...

持续集成交付CICD:Sonarqube自动更新项目质量配置

目录 一、实验 1.Sonarqube手动自定义质量规则并指定项目 2.Sonarqube自动更新项目质量配置 一、实验 1.Sonarqube手动自定义质量规则并指定项目 &#xff08;1&#xff09;自定义质量规则 ①新配置 ②更多激活规则③根据需求激活相应规则④已新增配置 ⑤ 查看 &#x…...

Linux设置Docker自动创建Nginx容器脚本

文章目录 前言一、本地新建脚本二、复制本地脚本到服务器三、执行服务器脚本总结如有启发&#xff0c;可点赞收藏哟~ 前言 一、本地新建脚本 在本地新建nginx-generator.sh脚本文件&#xff0c;并保存以下内容 主要动态定义两个变量&#xff08;容器名称/服务器本地文件名、端…...

技术博客:Vue中各种混淆用法汇总

技术博客&#xff1a;Vue中各种混淆用法汇总 摘要 本文主要介绍了在Vue中使用的一些常见混淆用法&#xff0c;包括new Vue()、export default {}、createApp()、Vue.component、Vue3注册全局组件、Vue.use()等&#xff0c;以及如何使用混淆器对代码进行加固&#xff0c;保护应…...

【python】Python生成GIF动图,多张图片转动态图,pillow

pip install pillow 示例代码&#xff1a; from PIL import Image, ImageSequence# 图片文件名列表 image_files [car.png, detected_map.png, base64_image_out.png]# 打开图片 images [Image.open(filename) for filename in image_files]# 设置输出 GIF 文件名 output_g…...

python/matlab图像去雾/去雨综述

图像去雾和去雨是计算机视觉领域的两个重要任务&#xff0c;旨在提高图像质量和可视化效果。本文将综述图像去雾和去雨的算法、理论以及相关项目代码示例。 一、图像去雾算法 基于暗通道先验的方法&#xff1a; 这是广泛应用于图像去雾的经典算法之一。该方法基于一个观察&…...

Docker+jenkins+gitlab实现持续集成

1.安装环境 服务器ip虚拟机版本192.168.5.132centos7.6192.168.5.152centos7.6 2. 安装docker 安装必要的一些系统工具 yum install -y yum-utils device-mapper-persistent-data lvm2添加软件源信息&#xff0c;要确保centos7能上外网 yum-config-manager --add-repo http:…...

Web前端JS如何获取 Video/Audio 视音频声道(左右声道|多声道)、视音频轨道、音频流数据

写在前面&#xff1a; 根据Web项目开发需求&#xff0c;需要在H5页面中&#xff0c;通过点击视频列表页中的任意视频进入视频详情页&#xff0c;然后根据视频的链接地址&#xff0c;主要是 .mp4 文件格式&#xff0c;在进行播放时实时的显示该视频的音频轨道情况&#xff0c;并…...

MySQL生成UUID并去除-

uuid()函数 uuid() 函数可以使mysql生成uuid,但是uuid中存在-,如下图&#xff1a; 去除uuid的- 默认生成的uuid含有-&#xff0c;我们可以使用replace函数替换掉-&#xff0c;SQL如下 select replace(uuid(),"-","") as uuid;Insert语句中使用UUID 如果…...

包与字符串

包是分类管理的需要&#xff0c;建立包用:package&#xff0c;包中类的引用import 学习使用javaAPI中的字符串类String&#xff0c;学会其成员方法的使用 &#xff08;必看&#xff09;eclipse包的分层等级结构设置 因为eclipse的包的结构默认是平行等级的&#xff0c;所以要手…...

【Gradle】mac环境安装Gradle及配置

官网安装说明&#xff1a;Gradle | Installation 由于Gradle运行依赖jvm&#xff0c;所以事先需要安装jdk&#xff0c;并确认你的jdk版本和gradle版本要求的对应关系&#xff0c;这个官网上有说明&#xff0c;但是我试了一下不太准确&#xff0c;供参考&#xff0c;链接如下&a…...

使用C语言操作kafka ---- librdkafka

1 安装librdkafka git clone https://github.com/edenhill/librdkafka.git cd librdkafka git checkout v1.7.0 ./configure make sudo make install sudo ldconfig 在librdkafka的examples目录下会有示例程序。比如consumer的启动需要下列参数 ./consumer <broker> &…...

误用STM32串口发送标志位 “USART_FLAG_TXE” “USART_FLAG_TC”造成的BUG

当你使用串口发送数据时是否出现过这样的情况&#xff1a; 1.发送时第一个字节丢失。 2.发送时出现莫名的字节丢失。 3.各种情况字节丢失。 1.先了解一下串口发送的流程图&#xff08;手动描绘&#xff09;&#xff1a; 可以假想USART_FLAG_TXE是用于检测"弹仓"&…...

指针(三)

函数指针 定义&#xff1a;整型指针是指向整形的指针,数组指针式指向数组的指针,其实函数指针就是指向函数的指针。 函数指针基础&#xff1a; &#xff08;&#xff09;优先级要高于*&#xff1b;一个变量除去了变量名&#xff0c;便是它的变量类型&#xff1b;一个指针变量…...

labelimg遇到的标签修改问题:修改一张图像的标签时,保存后导致classes.txt改变

问题描述&#xff1a;修改一张图像的标签时候&#xff0c; classes.txt 会同步更新&#xff0c;导致重新生成了 classes.txt 但是这个 classes.txt 只有你现在写的那个类别名&#xff0c;以前的没有了。 解决&#xff1a;设置一个 predefined_classes.txt&#xff0c;内容和模…...

Spring Cloud Gateway使用和配置

Spring Cloud Gateway是Spring官方基于Spring 5.0&#xff0c;Spring Boot 2.0和Project Reactor等技术开发的网关&#xff0c;Spring Cloud Gateway旨在为微服务架构提供一种简单而有效的统一的API路由管理方式。Spring Cloud Gateway作为Spring Cloud生态系中的网关&#xff…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...