当前位置: 首页 > 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…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...