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

组合求和-矩阵连乘所有加括号方式_2023_08_12

矩阵链加括号方式总数

  1. 前言

矩阵链乘积的瓶颈在于其标量运算的次数,不同的结合次序对其时间性能影响远大于矩阵乘积运算本身,可以看到许多教材上把求解矩阵标量运算的最优解作为动态规划的示例,问题隐含动态规划两大特征: 最优子结构及重叠子问题。诸多教材上对此作了详细的描述和解释,此问题本文不再做过多讨论。

本文旨在讨论给定某个矩阵,讨论其不同加括号的方式,要求求出所有可能加括号的数量,并就此问题引出Catalan Number的一般概念。

  1. 问题描述

给定矩阵<M1,M2,…Mn>,探索其可能加括号的方式。为了解决此问题,从最简单形式开始逐步进行研究其解的形式,假定只有一个矩阵M1, 那么其加括号的方式为1。同理,给定两个矩阵,显而易见,其加括号方式总数也为1。那么对于n个矩阵,那么其加括号的总数为几多呢?

为了探讨此一般解问题,假定第 k个矩阵把n个矩阵分两部分,表示第一部分矩阵为<M1,M2,…Mk>,表示第二部分矩阵为<Mk+1,M2,…Mn>。规定P(n)代表n个矩阵所有可能加括号方式的综合,可采用下列递归方程式表示其值,
P ( n ) = ∑ k = 1 n − 1 P ( k ) ∗ P ( n − k ) ; ( n ≥ 2 ) P(n)=\sum_{k=1}^{n-1}{P(k)*P(n-k)} ;\ (n\geq2) P(n)=k=1n1P(k)P(nk); (n2)
很明显,问题纳入分治的范畴,它之和子问题的长度相关的乘积相关,矩阵本身对其没有影响,P(k)代表k个矩阵可能的加括号方式,P(n-k)代表n-k个矩阵加括号方式,P(k)*P(n-k)代表以k为分界的所有加括号的方式,而P(k)*P(n-k)对于所有的k的方式求和,便是P(n)的值。

  1. 暴力递归方案(无记忆递归)

上述表达式为经典的递归求和方式,可以利用暴力求解途径,对每个n和k分割进行求解,最后求和即可得到最终的结果,它的时间复杂度与求解Catalan number相同(Program for nth Catalan Number - GeeksforGeeks),采用暴力方法求解的时间复杂度为Ω(4n/n3/2),暴力解决方法不是理想求解问题的方式,下一篇幅中将引入动态规划的途径求解。

通过观察发现,n==1的情况下构成递归的基础解,函数直接返回1作为递归结束点。定义 sum为不同加括号的方式,它可以与上级栈的乘积和进行累加。

深入探索就会发现f(n-i)和f(i)递归函数存在可能的重合部分,这将导致每次递归都到出口点,对函数计算构成严重浪费的行为。

int find_matrix_complete_parenthesis_recursion(int n)
{int i;int sum;if(n==1){return 1;}sum=0;for(i=1;i<n;i++){sum += find_matrix_complete_parenthesis_recursion(n - i) * \find_matrix_complete_parenthesis_recursion(i);}return sum;}
  1. 动态规划方案

上节讨论展开过程中,发现求解过程存在诸多重复子问题,虽然求和过程未呈现显著的最优子问题特征,原因在于其行为是对不同问题进行求和,求和过程本来就无所谓的最优/最劣的过程,它关注的是加括号方式的不同类型的求和。

int find_matrix_complete_parenthesis_dp(int n)
{int i;int j;int dp[n+1];memset(dp,0,sizeof(dp));dp[1]=1;for(i=2;i<=n;i++){for(j=1;j<i;j++){dp[i]+=dp[j]*dp[i-j];}}return dp[n];
}
  1. 总结

求解组合总和,一般不涉及到求解最大或最小值的操作,其过程汇总也不涉及到选择的代价,因为需要对所有的可能性选择进行求和汇总。

参考资料

  1. Program for nth Catalan Number - GeeksforGeeks

相关文章:

组合求和-矩阵连乘所有加括号方式_2023_08_12

矩阵链加括号方式总数 前言 矩阵链乘积的瓶颈在于其标量运算的次数&#xff0c;不同的结合次序对其时间性能影响远大于矩阵乘积运算本身&#xff0c;可以看到许多教材上把求解矩阵标量运算的最优解作为动态规划的示例&#xff0c;问题隐含动态规划两大特征&#xff1a; 最优子…...

《3D 数学基础》12 几何图元

目录 1 表达图元的方法 1.1 隐式表示法 1.2 参数表示 1.3 直接表示 2. 直线和射线 2.1 射线的不同表示法 2.1.1 两点表示 2.1.2 参数表示 2.1.3 相互转换 2.2 直线的不同表示法 2.2.1 隐式表示法 2.2.2 斜截式 2.2.3 相互转换 3. 球 3.1 隐式表示 1 表达图元的方…...

【设计模式——学习笔记】23种设计模式——备忘录模式Memento(原理讲解+应用场景介绍+案例介绍+Java代码实现)

案例引入 游戏角色有攻击力和防御力&#xff0c;在大战Boss前保存自身的状态(攻击力和防御力)&#xff0c;当大战Boss后攻击力和防御力下降&#xff0c;可以从备忘录对象恢复到大战前的状态 传统设计方案 针对每一种角色&#xff0c;设计一个类来存储该角色的状态 【分析】…...

致谢丨感谢有你,JumpServer开源项目九周年致谢名单

2014年到2023年&#xff0c;JumpServer开源项目已经走过了九年的时间。感谢以下社区贡献者对JumpServer项目的帮助和支持。 因为有你&#xff0c;一切才能成真。 JumpServer开源项目贡献者奖杯将于近日邮寄到以上贡献者手中&#xff0c;同时JumpServer开源项目组还准备了一份小…...

使用 Python 和 Flask 构建简单的 Restful API 第 1 部分

一、说明 我将把这个系列分成 3 或 4 篇文章。在本系列的最后&#xff0c;您将了解使用flask构建 restful API 是多么容易。在本文中&#xff0c;我们将设置环境并创建将显示“Hello World”的终结点。 我假设你的电脑上安装了python 2.7和pip。我已经在python 2.7上测试了本文…...

【深度学习所有损失函数】在 NumPy、TensorFlow 和 PyTorch 中实现(2/2)

一、说明 在本文中&#xff0c;讨论了深度学习中使用的所有常见损失函数&#xff0c;并在NumPy&#xff0c;PyTorch和TensorFlow中实现了它们。 (二-五)见 六、稀疏分类交叉熵损失 稀疏分类交叉熵损失类似于分类交叉熵损失&#xff0c;但在真实标签作为整数而不是独热编码提…...

Hazel 引擎学习笔记

目录 Hazel 引擎学习笔记学习方法思考引擎结构创建工程程序入口点日志系统Premake\MD没有 cpp 文件的项目会出错include 到某个库就要包含这个库的路径&#xff0c;注意头文件展开 事件系统 获取和利用派生类信息预编译头文件抽象窗口类和 GLFWgit submodule addpremake 脚本禁…...

Linux系统下Redis3.2集群

本节主要学习reids主从复制的概念&#xff0c;作用&#xff0c;缺点&#xff0c;流程&#xff0c;搭建&#xff0c;验证&#xff0c;reids哨兵模式的概念&#xff0c;作用&#xff0c;缺点&#xff0c;结构&#xff0c;搭建&#xff0c;验证等。 文章目录 一、redis主从复制 …...

Android图形-合成与显示-SurfaceTestDemo

目录 引言&#xff1a; 主程序代码&#xff1a; 结果呈现&#xff1a; 小结&#xff1a; 引言&#xff1a; 通过一个最简单的测试程序直观Android系统的native层Surface的渲染显示过程。 主程序代码&#xff1a; #include <cutils/memory.h> #include <utils/L…...

高压放大器怎么设计(高压放大器设计方案)

高压放大器是一种用于将低电压信号转换成高电压信号的电子设备&#xff0c;广泛应用于通信、雷达、医疗设备等领域。在设计高压放大器时&#xff0c;需要考虑多种因素&#xff0c;如输入输出信号的特性、电路结构的选择、电源和负载匹配等。本文将介绍高压放大器的设计方法和注…...

SpringBoot yml配置注入

yaml语法学习 1、配置文件 SpringBoot使用一个全局的配置文件 &#xff0c; 配置文件名称是固定的 application.properties 语法结构 &#xff1a;keyvalue application.yml 语法结构 &#xff1a;key&#xff1a;空格 value 配置文件的作用&#xff1a;修改SpringBoot自动…...

中科亿海微乘法器(LPMMULT)

引言 FPGA&#xff08;可编程逻辑门阵列&#xff09;是一种可在硬件级别上重新配置的集成电路。它具有灵活性和可重构性&#xff0c;使其成为处理各种应用的理想选择&#xff0c;包括数字信号处理、图像处理、通信、嵌入式系统等。在FPGA中&#xff0c;乘法器是一种重要的硬件资…...

Redis_持久化(AOF、RDB)

6. Redis AOF 6.1 简介 目前&#xff0c;redis的持久化主要应用AOF&#xff08;Append Only File&#xff09;和RDF两大机制&#xff0c;AOF以日志的形式来记录每个写操作&#xff08;增量保存&#xff09;&#xff0c;将redis执行过的所有指令全部安全记录下来&#xff08;读…...

开源数据库Mysql_DBA运维实战 (部署服务篇)

前言❀ 1.数据库能做什么 2.数据库的由来 数据库的系统结构❀ 1.数据库系统DBS 2.SQL语言(结构化查询语言) 3.数据访问技术 部署Mysql❀ 1.通过rpm安装部署Mysql 2.通过源码包安装部署Mysql 前言❀ 1.数据库能做什么 a.不论是淘宝&#xff0c;吃鸡&#xff0c;爱奇艺…...

【Java学习】System.Console使用

背景 在自学《Java核心技术卷1》的过程中看到了对System.Console的介绍&#xff0c;编写下列测试代码&#xff0c; public class ConsoleTest {public static void main(String[] args) {Console cs System.console();String name cs.readLine("AccountInfo: ");…...

从零学算法154

154.已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到&#xff1a; 若旋转 4 次&#xff0c;则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次&#…...

95 | Python 设计模式 —— 策略模式

策略模式(Strategy Pattern) 引言 策略模式是一种行为型设计模式,它定义了一系列的算法,并将每个算法封装在独立的策略类中,使得这些算法可以相互替换,而不影响客户端的使用。策略模式可以让客户端根据不同的需求选择不同的算法,从而使得系统更加灵活和可扩展。 在本…...

【BASH】回顾与知识点梳理(十九)

【BASH】回顾与知识点梳理 十九 十九. 循环 (loop)19.1 while do done, until do done (不定循环)19.2 for...do...done (固定循环)19.3 for...do...done 的数值处理(C写法)19.4 搭配随机数与数组的实验19.5 shell script 的追踪与 debug19.6 what_to_eat-2.sh debug结果解析 该…...

Selenium之css怎么实现元素定位?

世界上最远的距离大概就是明明看到一个页面元素站在那里&#xff0c;但是我却定位不到&#xff01;&#xff01; Selenium定位元素的方法有很多种&#xff0c;像是通过id、name、class_name、tag_name、link_text等等&#xff0c;但是这些方法局限性太大&#xff0c; 随着自动…...

计算机基础之RAID技术

概述 RAID&#xff0c;Redundant Array of Independent Disks&#xff0c;独立磁盘冗余阵列&#xff0c;一种把多块独立的硬盘&#xff08;物理硬盘&#xff09;按不同的方式组合起来形成一个硬盘组&#xff08;逻辑硬盘&#xff09;&#xff0c;从而提供比单个硬盘更高的存储…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

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

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

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

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

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

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...