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

15.2 矩阵链乘法

1.代码

public class MatrixChainMultiplication {public static void main(String[] args) {
//        在该代码中,我们首先创建了两个n * n的矩阵m和s,分别用于记录最优值和分割点。 其中m 矩阵 通过i j 来显示在i到j的矩阵链中最优解
//
//        然后,我们将i = j时的m[i][j]赋值为0,因为一个矩阵的乘积为0。
//
//        接下来,我们使用L循环枚举子问题规模,i循环枚举左端点,j循环枚举右端点,并使用k循环枚举分割点。
//
//        对于每个分割点k,我们计算最优值q,然后将q与m[i][j]进行比较,如果q小于m[i][j],则更新m[i][j]和s[i][j]。
//        通过公式算法导论15.7
//
//        最后,我们返回m[1][n-1],即原问题的最优值。
//
//        该算法的时间复杂度为O(n^3),其中n是矩阵的数量。int[] p = {30, 35, 15, 5, 10, 20, 25};System.out.println("最少的乘法次数为:" + matrixChainOrder(p));}
​public static int matrixChainOrder(int[] p) {int n = p.length;// 创建n * n的矩阵m和s,用于记录最优值和分割点int[][] m = new int[n][n];int[][] s = new int[n][n];// i==j时,m[i][j]=0,因为一个矩阵的乘积为0for (int i = 1; i < n; i++) {m[i][i] = 0;}for (int i = 0; i < m.length; i++) {System.out.println(Arrays.toString(m[i]));}
​// L是子问题规模for (int L = 2; L < n; L++) {// i是左端点,j是右端点,k是分割点for (int i = 1; i < n - L + 1; i++) {int j = i + L - 1;m[i][j] = Integer.MAX_VALUE;// 枚举分割点k,求解最优值for (int k = i; k < j; k++) {int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];System.out.println("m[i][k]: "+m[i][k] );System.out.println("m[k + 1][j]: "+m[k + 1][j]);System.out.println("i:"+i+" k:"+k+" j:"+j);System.out.println(q);if (q < m[i][j]) {m[i][j] = q;s[i][j] = k;}}}}// 返回最优值return m[1][n - 1];}
​
​
}

2.原理

自己看算法导论吧

我再看到

这条公式的时候很困惑,然后自己手算了他给的第一个例子才知道这是正确的.

3.问题

具体的问题已经在代码注释中讲解完毕

4.进阶

输出只是I一个普通的递归而已

package collection;
​
public class printOptimalParens {public static void matrixChainOrder(int[] p) {int n = p.length - 1;int[][] m = new int[n + 1][n + 1];int[][] s = new int[n + 1][n + 1];for (int i = 1; i <= n; i++) {m[i][i] = 0;}for (int len = 2; len <= n; len++) {for (int i = 1; i <= n - len + 1; i++) {int j = i + len - 1;m[i][j] = Integer.MAX_VALUE;for (int k = i; k <= j - 1; k++) {int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];if (q < m[i][j]) {m[i][j] = q;s[i][j] = k;}}}}System.out.println("Optimal Parenthesization:");printOptimalParens(s, 1, n);}
​public static void printOptimalParens(int[][] s, int i, int j) {if (i == j) {System.out.print("A" + i);} else {System.out.print("(");printOptimalParens(s, i, s[i][j]);printOptimalParens(s, s[i][j] + 1, j);System.out.print(")");}}
​public static void main(String[] args) {int[] p = {30, 35, 15, 5, 10, 20, 25};matrixChainOrder(p);}
}
​
​
((A1(A2A3))((A4A5)A6))

相关文章:

15.2 矩阵链乘法

1.代码 public class MatrixChainMultiplication {public static void main(String[] args) { // 在该代码中&#xff0c;我们首先创建了两个n * n的矩阵m和s&#xff0c;分别用于记录最优值和分割点。 其中m 矩阵 通过i j 来显示在i到j的矩阵链中最优解 // // …...

向隐形冠军学习:聚焦人效,用时间管理提效益

注&#xff1a; 本文来源于盖雅工场联合创始人兼CEO 章新波 在2023狮山论坛“ 向隐形冠军学习&#xff1a; 聚焦人效&#xff0c;用时间管理提效益 ”的主题分享。 文&#xff5c;章新波 整理 &#xff5c;盖雅学苑 在人力资源行业以及各大企业&#xff0c;「人效」这个词…...

Protocol Buffers Go Generated Code Guide

Protocol Buffers Go 代码生成指南 本主题准确描述了协议缓冲区编译器为任何给定的协议定义生成的Go代码。 编译器调用 协议缓冲区编译器需要一个插件来生成Go 代码。使用Go 1.16或更高版本安装&#xff0c;方法是运行&#xff1a; go install google.golang.org/protobuf/…...

Python VTK STL 映射三维模型表面距离

目录 前言&#xff1a; 效果&#xff1a; 实现步骤&#xff1a; Code: 前言&#xff1a; 本文介绍了Python VTK映射三维模型表面距离&#xff0c;通过如何使用VTK计算两个三维模型(stl)的表面距离&#xff0c;并将其距离值以颜色映射到模型&#xff0c;可用于对比 两相模型…...

C# 异常处理机制和常见的异常类型

在 C# 中&#xff0c;异常处理是一个非常重要的概念&#xff0c;它可以让我们在程序发生错误时进行有效的处理&#xff0c;使程序具备更好的鲁棒性。C# 异常处理机制基于 try-catch-finally 语句块&#xff0c;其基本用法如下&#xff1a; try {// 可能会抛出异常的代码 } cat…...

【0187】客户端身份验证配置文件视图之pg_hba_file_rules

文章目录 1. 客户端身份验证配置文件视图2. 视图效果相关阅读: 【0179】配置PostgreSQL以允许远程连接 【0180】PG内核通过pg_hba.conf完成客户端认证(1) 【0181】PG内核通过pg_hba.conf完成客户端认证(2)...

模糊层次分析法(FAHP)Python实现

文章目录 理论基础三角模糊数概念参考 Python源码测试 理论基础 \quad 模糊层次分析法&#xff08; F A H P FAHP FAHP&#xff09;将模糊理论&#xff08; F u z z y S e t Fuzzy Set FuzzySet&#xff09;嵌入到基本层次分析法&#xff08; A H P AHP AHP&#xff09;中。 A …...

gdb切换窗口焦点

为了辅助调试&#xff0c;一般会使用layout src&#xff0c;调起TUI显示代码&#xff1a; 然而这种情况下我们写命令很不方便&#xff0c;无法方便地使用上一条命令、退格等。 按动上下左右方向键盘只会移动代码框&#xff0c;然而在伪终端下&#xff0c;可以用鼠标滚轮来上下…...

【Spring Security】 入门实战

文章目录 一、基本概念二、Spring Security第一个程序三、Spring Security没有生效四、修改默认账号密码&#xff08;appliction.yml&#xff09;五、修改默认账号密码&#xff08;配置类&#xff09;六、Spring Security的三个configure方法七、Spring Security的三种身份的验…...

SpringBoot的Interceptor拦截器的简介和实际使用

拦截器&#xff08;Interceptor&#xff09; 概念&#xff1a;是一种动态拦截方法调用的机制&#xff0c;类似于过滤器。Spring框架中提供的&#xff0c;用来动态拦截控制器方法的执行。 作用&#xff1a;拦截请求&#xff0c;在指定的方法调用前后&#xff0c;根据业务需要执行…...

5个面向Python高级开发者的技巧

使用这些用于自定义类行为、编写并发代码、管理资源、存储和操作数据以及优化代码性能的高级技术来探索 Python 的深度。 本文探讨了 Python 中的五个高级主题&#xff0c;它们可以为解决问题和提高代码的可靠性和性能提供有价值的见解和技术。从允许您在定义类时自定义类行为的…...

Nginx简介

Nginx是什么&#xff1f;可以做什么事情&#xff1f; Nginx是高性能的HTTP和反向代理的web服务器&#xff0c;处理高并发的能力十分强大&#xff0c;能经受高负载的考研&#xff0c;有报告表明能能支持高达50000个并发连接数。 特点 占有内存少&#xff1a;一万个长连接&…...

十五分钟带你学会 Electron

文章目录 什么是 Electron为什么要选择 Electron安装 Electron桌面CSDN实战Electron 基础配置Electron 进程主进程渲染进程主进程与渲染进程的区别主进程与渲染进程的通信 Electron 跨平台问题Electron 部署打包应用程序发布应用程序 Electron 跨端原理总结 什么是 Electron E…...

设计模式-结构型模式之桥接模式

2. 桥接模式 2.1. 模式动机 设想如果要绘制矩形、圆形、椭圆、正方形&#xff0c;我们至少需要4个形状类&#xff0c;但是如果绘制的图形需要具有不同的颜色&#xff0c;如红色、绿色、蓝色等&#xff0c;此时至少有如下两种设计方案&#xff1a; 第一种设计方案是为每一种形状…...

软件测试工程师为什么要写测试用例?

软件测试工程师为什么要写测试用例&#xff1f;相信从事软件测试行业的从业者来讲&#xff0c;测试用例并不陌生。因为测试用例不仅仅是一组简单的文档&#xff0c;它包含前提条件、输入、执行条件和预期结果等等重要内容&#xff0c;并且能够完成一定的测试目的和需求。下面本…...

【DAY40】VUE练习

DOS命令&#xff1a; DOS&#xff08;Disk Operating System&#xff09;是一种操作系统&#xff0c;它使用命令行界面&#xff08;Command Prompt&#xff09;进行交互。在 DOS 中&#xff0c;有一些常用的命令&#xff0c;可以用来定位目录、创建、删除、拷贝文件和目录&…...

实模式的寄存器

实模式的寄存器有8个通用寄存器&#xff0c;分别为AX、BX、CX、DX、SI、DI、BP和SP。通用的意思就是它们之中的大部分可以根据需要用于多种目的。 AX: accumulator&#xff0c;累加寄存器 BX: base&#xff0c;基址寄存器 CX: count&#xff0c;计数寄存器 SI: Source Index&am…...

【UE 控件蓝图】通过键盘选中要点击的按钮 通过Enter键点击

上一篇【UE 控件蓝图】菜单及功能实现博客已经完成了菜单的制作&#xff0c;但是我们只能通过鼠标来点击菜单选项&#xff0c;本篇博客实现的是能够通过键盘的上下键来选中按钮&#xff0c;然后按下“Enter”键来实现点击按钮的效果。 效果 可以看到并没有移动鼠标也可以通过…...

SSR在天猫优品大促会场的探索实践

BBC 发现其网站加载时间每增加一秒&#xff0c;用户便会流失 10%。为提高页面的秒开率&#xff0c;我们不断探索着优化策略&#xff0c;仅仅在浏览器领域下的优化已经满足不了我们的极致要求&#xff0c;开始往服务端方向不断探索。本文将讨论业务接入SSR的几个问题&#xff1a…...

WPF教程(一)---创建一个WPF程序基础知识

1.前言&#xff1a; 这篇主要讲WPF的开发基础&#xff0c;介绍了如何使用Visual Studio 2019创建一个WPF应用程序。 首先说一下学习WPF的基础知识&#xff1a; 1) 要会一门.NET所支持的编程语言--例如C#。 2) 会一点“标准通用标记语言”&#xff1a;WPF窗体程序使用的XAML语…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

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

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

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...