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

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...