连接两组点的最低成本
来源:dev.to
2024-11-25 16:10:40
0浏览
收藏
你在学习文章相关的知识吗?本文《连接两组点的最低成本》,主要介绍的内容就涉及到,如果你想提升自己的开发能力,就不要错过这篇文章,大家要知道编程理论基础和实战操作都是不可或缺的哦!
1595。连接两组点的最低成本
难度:难
主题:数组、动态规划、位操作、矩阵、位掩码
给你两组点,第一组有大小1点,第二组有大小2点,大小1 >=尺寸2.
任意两点之间的连接成本以大小 1 x size2 矩阵给出,其中 cost[i][j] 是连接点 i 的成本第一组和第二组的 j 点。如果两个组中的每个点都连接到相反组中的一个或多个点,则这些组已连接。换句话说,第一组中的每个点必须连接到第二组中的至少一个点,第二组中的每个点必须连接到第一组中的至少一个点。
返回连接两个组所需的最低成本。
示例1:
- 输入: 成本 = [[15, 96], [36, 2]]
- 输出: 17
- 说明:连接组的最佳方式是:
1--a 2--b this results in a total cost of 17.
示例2:
- 输入: 成本 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
- 输出: 4
- 说明:连接组的最佳方式是:
1--a 2--b 2--c 3--a this results in a total cost of 4.
请注意,有多个点连接到第一组中的点 2 和第二组中的点 a。这并不重要,因为可以连接的点数没有限制。我们只关心最低的总成本。
示例 3:
- 输入: 成本 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
- 输出: 10
约束:
- 大小1 == cost.length
- 大小2 == 成本[i].长度
- 1 <= 大小1,大小2 <= 12
- 大小1 >=大小2
- 0 <= 成本[i][j] <= 100
提示:
- 左侧的每个点要么连接到已连接到某个左侧节点的精确点,要么连接到右侧未连接到任何节点的节点的子集
- 使用带有位掩码的动态规划,其中状态将为(第一组中分配的点的数量,第二组中分配的点的位掩码)。
解决方案:
我们可以利用带有位掩码的动态编程。这个想法是通过考虑第一组中的每个点并尝试将其连接到第二组中的所有点来最小化成本。
具有位掩码的动态规划 (dp) 方法
步骤:
-
国家代表:
- 使用 dp 表 dp[i][mask],其中:
- i 是第一组中的索引(范围从 0 到 size1-1)。
- mask 是一个位掩码,表示第二组中的哪些点已连接。
- 使用 dp 表 dp[i][mask],其中:
-
状态转换:
- 对于第一组中的每个点,尝试将其连接到第二组中的每个点,相应地更新 dp 表。
- 如果连接了第二组中的新点,则更新掩码中的相应位。
-
基本案例:
- 从 dp[0][0] = 0 开始(最初没有连接)。
-
目标:
- 计算 dp[size1][(1 << size2) - 1] 的最小成本,它表示连接两组中的所有点。
让我们用 php 实现这个解决方案:1595。连接两组点的最低成本
<?php /** * @param Integer[][] $cost * @return Integer */ function connectTwoGroups($cost) { ... ... ... /** * go to ./solution.php */ } // Example usage: $cost1 = [[15, 96], [36, 2]]; $cost2 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]; $cost3 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]; echo connectTwoGroups($cost1) . "\n"; // Output: 17 echo connectTwoGroups($cost2) . "\n"; // Output: 4 echo connectTwoGroups($cost3) . "\n"; // Output: 10 ?>
解释:
- dp 数组 dp[i][mask] 存储将第 1 组中的前 i 个点与第 2 组中的点连接起来的最小成本,如 mask 所示。
- 嵌套循环迭代 i 和 mask 的每个组合,尝试通过考虑所有可能的连接来找到最佳成本。
- 最终,该解决方案会考虑第二组中某些点可能仍未连接的情况来计算最小成本,确保所有点都已连接。
这种方法有效地处理了问题的约束,并确保连接两个组的成本最小。
联系链接
如果您发现本系列有帮助,请考虑在 github 上给存储库 一颗星,或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- github
终于介绍完啦!小伙伴们,这篇关于《连接两组点的最低成本》的介绍应该让你收获多多了吧!欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识,快来关注吧!
版本声明
本文转载于:dev.to 如有侵犯,请联系study_golang@163.com删除

- 上一篇
- 苹果电脑创建分区不能选择分区表格式?

- 下一篇
- NodeJS模块【简单说明】
查看更多
最新文章
-
- 文章 · php教程 | 6分钟前 |
- Laravel8+调用MySQL存储过程教程
- 206浏览 收藏
-
- 文章 · php教程 | 7分钟前 |
- Symfony获取IP地理位置并转数组方法
- 490浏览 收藏
-
- 文章 · php教程 | 18分钟前 |
- 图片水印添加教程:GD库使用详解
- 125浏览 收藏
-
- 文章 · php教程 | 43分钟前 | php
- PHP多语言网站变现策略与本地化方案
- 147浏览 收藏
-
- 文章 · php教程 | 51分钟前 |
- PHP5.6兼容PHP7类型声明替换方法
- 278浏览 收藏
-
- 文章 · php教程 | 54分钟前 |
- LaravelupdateOrCreate累加技巧分享
- 292浏览 收藏
-
- 文章 · php教程 | 59分钟前 | php 内存限制 分批处理 ini_set() set_time_limit()
- PHP导入大数据时临时增加内存限制方法
- 334浏览 收藏
-
- 文章 · php教程 | 1小时前 | 调试 SEO .htaccess mod_rewrite PHPURL重写
- PHPURL重写教程:.htaccess配置详解
- 137浏览 收藏
-
- 文章 · php教程 | 1小时前 |
- 递归清理空分类,结构优化教程
- 381浏览 收藏
-
- 文章 · php教程 | 1小时前 |
- PHPDirectoryIterator自然排序技巧
- 129浏览 收藏
查看更多
课程推荐
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 511次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 498次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 484次学习
查看更多
AI推荐
-
- 千音漫语
- 千音漫语,北京熠声科技倾力打造的智能声音创作助手,提供AI配音、音视频翻译、语音识别、声音克隆等强大功能,助力有声书制作、视频创作、教育培训等领域,官网:https://qianyin123.com
- 167次使用
-
- MiniWork
- MiniWork是一款智能高效的AI工具平台,专为提升工作与学习效率而设计。整合文本处理、图像生成、营销策划及运营管理等多元AI工具,提供精准智能解决方案,让复杂工作简单高效。
- 162次使用
-
- NoCode
- NoCode (nocode.cn)是领先的无代码开发平台,通过拖放、AI对话等简单操作,助您快速创建各类应用、网站与管理系统。无需编程知识,轻松实现个人生活、商业经营、企业管理多场景需求,大幅降低开发门槛,高效低成本。
- 169次使用
-
- 达医智影
- 达医智影,阿里巴巴达摩院医疗AI创新力作。全球率先利用平扫CT实现“一扫多筛”,仅一次CT扫描即可高效识别多种癌症、急症及慢病,为疾病早期发现提供智能、精准的AI影像早筛解决方案。
- 170次使用
-
- 智慧芽Eureka
- 智慧芽Eureka,专为技术创新打造的AI Agent平台。深度理解专利、研发、生物医药、材料、科创等复杂场景,通过专家级AI Agent精准执行任务,智能化工作流解放70%生产力,让您专注核心创新。
- 185次使用
查看更多
相关文章
-
- PHP技术的高薪回报与发展前景
- 2023-10-08 501浏览
-
- 基于 PHP 的商场优惠券系统开发中的常见问题解决方案
- 2023-10-05 501浏览
-
- 如何使用PHP开发简单的在线支付功能
- 2023-09-27 501浏览
-
- PHP消息队列开发指南:实现分布式缓存刷新器
- 2023-09-30 501浏览
-
- 如何在PHP微服务中实现分布式任务分配和调度
- 2023-10-04 501浏览