动态规划 剪绳子问题
给一段长度为n的绳子,请把绳子剪成m段,每段绳子的长度为k[0],k[1],k[2],k[3]....k[m].请问k[0]k[1]k[2].....*k[m]的最大乘积为多少
#include <vector> // 包含vector头文件
#include <algorithm> // 包含algorithm头文件,用于max函数class Solution { // 定义解决方案类
public:int cutRope(int n) { // 主函数,计算最大乘积if (n <= 1) return 0; // 如果绳子长度小于等于1,无法剪断if (n == 2) return 1; // 如果绳子长度为2,最大乘积为1if (n == 3) return 2; // 如果绳子长度为3,最大乘积为2std::vector<int> dp(n + 1, 0); // 创建动态规划数组,初始化为0// 初始化基础情况dp[0] = 0; // 长度为0的绳子乘积为0dp[1] = 1; // 长度为1的绳子乘积为1dp[2] = 2; // 长度为2的绳子乘积为2dp[3] = 3; // 长度为3的绳子乘积为3for (int i = 4; i <= n; i++) { // 从长度4开始计算for (int j = 1; j <= i / 2; j++) { // 尝试所有可能的切割点dp[i] = std::max(dp[i], dp[j] * dp[i - j]); // 更新最大乘积}}return dp[n]; // 返回长度为n的绳子的最大乘积}
};
这个实现使用了动态规划的方法来解决问题。以下是主要的设计思路:
- 我们定义了一个
Solution类,其中包含一个cutRope函数来解决这个问题。 - 首先,我们处理了一些特殊情况:
- 如果绳子长度小于等于1,无法剪断,返回0。
- 如果绳子长度为2,最大乘积为1(必须剪断)。
- 如果绳子长度为3,最大乘积为2(必须剪断)。
- 我们创建了一个动态规划数组
dp,其中dp[i]表示长度为i的绳子能得到的最大乘积。 - 初始化基础情况:
dp[0] = 0,dp[1] = 1,dp[2] = 2,dp[3] = 3- 注意,对于长度为2和3的情况,虽然必须剪断,但在作为子问题时,保持完整可能会得到更大的乘积。
- 然后,我们从长度4开始,逐步计算到长度n:
- 对于每个长度i,我们尝试所有可能的切割点j。
- 计算
dp[j] * dp[i-j],这代表将绳子切割成长度为j和i-j的两段。 - 使用
std::max函数来更新dp[i],保证它始终是最大的乘积。
- 最后,返回
dp[n],即为所求的最大乘积。
这个算法的时间复杂度为O(n^2),空间复杂度为O(n)。
当然可以使用更有效的解法,但是需要一点数学知识这个优化的算法基于一个数学发现:当绳子长度大于3时,尽可能多地切出长度为3的片段会得到最大乘积。如果最后剩下的长度为1,我们应该将其与一个3合并,形成一个长度为4的片段
class Solution { // 定义解决方案类
public:int cutRope(int n) { // 主函数,计算最大乘积if (n <= 3) return n - 1; // 处理特殊情况int quotient = n / 3; // 计算可以切出多少个长度为3的片段int remainder = n % 3; // 计算切完长度为3的片段后剩余的长度if (remainder == 0) { // 如果刚好被3整除return pow(3, quotient); // 返回3的quotient次方} else if (remainder == 1) { // 如果余1return pow(3, quotient - 1) * 4; // 最后的3和1合并为4} else { // 如果余2return pow(3, quotient) * 2; // 最后剩一个2}}private:int pow(int base, int exponent) { // 快速幂函数int result = 1; // 初始化结果为1while (exponent > 0) { // 当指数大于0时循环if (exponent & 1) { // 如果指数的二进制表示中当前位为1result *= base; // 将base乘到结果中}base *= base; // base自乘exponent >>= 1; // 指数右移一位}return result; // 返回结果}
};
相关文章:
动态规划 剪绳子问题
给一段长度为n的绳子,请把绳子剪成m段,每段绳子的长度为k[0],k[1],k[2],k[3]....k[m].请问k[0]k[1]k[2].....*k[m]的最大乘积为多少 #include <vector> // 包含vector头文件 #include <algorithm> // 包含algorithm头文件,用于m…...
上位机图像处理和嵌入式模块部署(mcu项目1:实现协议)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 这种mcu的嵌入式模块理论上都是私有协议,因为上位机和下位机都是自己开发的,所以只需要自己保证上、下位机可以通讯上&…...
【NLP学习笔记】load_dataset加载数据
除了常见的load_dataset(<hf上的dataset名>)这种方式加载HF上的所有数据外,还有其他custom的选项。 加载HF上部分数据 from datasets import load_dataset c4_subset load_dataset("allenai/c4", data_files"en/c4-train.0000*-of-01024.js…...
企业如何选择好用的供应商管理系统
供应商管理系统软件(SRM)是企业用于管理供应链中各个供应商关系的重要工具。现如今竞争激烈的市场环境下,选择一款合适的SRM软件显得尤为重要。那么,如何选择一款好用的供应商管理系统呢? 企业在选择好用的供应商管理…...
震惊!运气竟能如此放大!运气的惊人作用,你了解吗?
芒格:得到你想要的东西,最保险的办法,就是让自己配得上你想要的那个东西。今天仔细想了想这句话,他其实说的是无数成功人士的心声 —— “我配得上!” 美剧《绝命毒师》有个导演叫文斯吉里根(Vince Gilliga…...
记录一次Apache Tomcat 处理返回自定义的404页面
记录工作中遇到处理访问tomcat 不存在的资源,返回自定义的404页面 删除webapps目录下的example、docs、manager、hta-manager目录,只保留 ROOT目录,应用部署在了这个目录 删除 manager、hta-manager 我没有发现有什么异常 制作404.jsp 或者 4…...
【piania 的用法】
piania 的用法 定义store建议使用箭头函数TypeScript插件扩展1、全局添加对象 定义store import { ref, computed } from vue import { defineStore } from pinia // pinia 以函数的形式暴露出去 export const useCounterStore defineStore(counter, () > {// 1、ref 相当…...
上海计算机考研炸了,这所学校慎报!上海大学计算机考研考情分析!
上海大学(Shanghai University),简称“上大”,是上海市属、国家“211工程”重点建设的综合性大学,教育部与上海市人民政府共建高校,国防科技工业局与上海市人民政府共建高校,国家“双一流”世界…...
面对全球新能源汽车合作发展创维汽车如何实现共赢
由全球新能源汽车合作组织(筹)主办、中国电动汽车百人会承办的首届全球新能源汽车合作发展论坛(GNEV2024)于6月27日,6月28日在新加坡金沙会议展览中心召开。创维汽车国际营销公司总经理齐奎源受邀参会并作出分享。 本届大会以推动全球新能源汽车产业协同发展与合作…...
安全和加密常识(1)对称加密和非对称加密以及相应算法
文章目录 对称加密(Symmetric Encryption)非对称加密(Asymmetric Encryption)使用场景和优缺点对称加密和非对称加密是信息安全领域中两种重要的加密方式,它们分别使用不同的加密算法和密钥管理方式来保护数据的机密性。下面我来简单介绍一下它们及其相应的算法。 对称加…...
afrog-漏洞扫描(挖洞)工具【了解安装使用详细】
★★免责声明★★ 文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与学习之用,读者将信息做其他用途,由Ta承担全部法律及连带责任,文章作者不承担任何法律及连带责任。 1、afrog介绍 afrog 是一款性能卓越、快速稳定、PoC可定…...
c++类模板--无法解析的外部符号
解决办法 文章目录 解决办法方法1(推荐).在主函数包含头文件时将实现模板类的函数也包含进来方法2.将模板类的实现方法写在头文件里面方法3.函数模板声明前加inline 可能错误2,类内实现友元输出重载 方法1(推荐).在主函数包含头文件时将实现模板类的函数也包含进来 …...
Postman介绍
Postman 是一款流行的 API 开发和测试工具,它提供了一个直观的用户界面,使开发者可以轻松地构建、测试和修改 HTTP 请求。Postman 不仅适用于测试人员,也广泛应用于开发人员、产品经理和API设计者中,以确保API的正确性和性能。 以…...
以智能化为舵手,引领现代计算机系统架构新航向
编者按:如今计算机系统承载的服务和算法逻辑日益复杂,理解、设计并改进计算机系统已成为核心挑战。面对系统复杂度和规模的指数级增长,以及新的大模型驱动场景下的分布式系统形态的涌现,人们亟需创新方法与技术来应对。在计算机系…...
揭秘品牌成功秘诀:品牌营销策略的核心要素大公开
品牌营销作为企业战略中至关重要的一环,其核心是建立和传播品牌的独特魅力,使其在消费者心目中占据重要位置。 一个成功的品牌营销策略能够提升品牌的知名度和影响力,带来持续的销售和忠诚客户群体。 在当今竞争激烈的市场环境中࿰…...
java如何把list转换成map
不废话,直接上代码 public static void main(String[] args) {List<UserxVO> list new ArrayList<>();for (int i 0; i < 10; i) {list.add(new UserxVO("n" i, "dd" i));}Map<String, String> map list.stream().co…...
vite typescript 配置跨域代理
打开工程目录下vite.config.ts文件 export default defineConfig({plugins: [vue(), topLevelAwait()],resolve: { alias },server:{proxy:{/api:{ //对以 /api 开头的请求跨域处理target:http://xxx.xxx.cn,//目标服务器changeOrigin: true,rewrite:(path)>{return path.…...
ArcGIS Pro SDK (七)编辑 10 捕捉
ArcGIS Pro SDK (七)编辑 10 捕捉 文章目录 ArcGIS Pro SDK (七)编辑 10 捕捉1 配置捕捉 - 打开或关闭捕捉2 配置捕捉 - 应用程序捕捉模式3 配置捕捉 - 图层捕捉可捕捉性4 配置捕捉 - 图层捕捉模式5 配置捕捉 - 组合示例6 捕捉选项…...
开始尝试从0写一个项目--后端(一)
创建文件的目录结构 利用这个界面创建 序号 名称 说明 1 SEMS maven父工程,统一管理依赖版本,聚合其他子模块 2 sems-common 子模块,存放公共类,例如:工具类、常量类、异常类等 3 sems-pojo 子模块&#x…...
STM32第十二课:ADC检测烟雾浓度(MQ2)
文章目录 需求一、MQ-2 气体传感器特点应用电路及引脚 二、实现流程1.开时钟,分频,配IO2.配置ADC的工作模式3.配置通道4.复位,AD校准5.数值的获取 需求实现总结 需求 使用ADC将MQ2模块检测到的烟雾浓度模拟量转化为数字量。 最后,…...
基于MAX78000与CNN的智能螺栓巡检小车:嵌入式AI实战解析
1. 项目概述与核心思路在轨道交通的日常运维中,螺栓的紧固状态检查是一项繁重且关键的任务。无论是轨道上的紧固螺栓,还是列车转向架、轮对轴承上的关键螺栓,其松动或失效都可能引发严重的安全事故。传统的人工巡检方式不仅效率低下ÿ…...
告别KITTI!用TartanAir数据集在Unreal Engine+AirSim里复现那些让VSLAM算法“翻车”的雨天和黑夜
超越KITTI:用TartanAir数据集在虚拟极端环境中锤炼VSLAM算法当视觉SLAM算法在KITTI数据集上取得95%的准确率时,开发者们常常会松一口气——直到这些算法被部署到真实世界的雨夜街道上。突然之间,那些在阳光明媚的德国道路上表现优异的特征点检…...
BetterNCM安装器终极指南:5分钟解锁网易云音乐无限潜能
BetterNCM安装器终极指南:5分钟解锁网易云音乐无限潜能 【免费下载链接】BetterNCM-Installer 一键安装 Better 系软件 项目地址: https://gitcode.com/gh_mirrors/be/BetterNCM-Installer 你是否觉得网易云音乐PC版功能有限,界面单调?…...
绝了!原来毕业论文还能这样写?2026降AIGC工具推荐合集
还在为查重率爆红、AI痕迹太明显、格式乱成一团而发愁?2026 年的 AI 论文工具早已不只是写文章那么简单,从选题构思到降AIGC率、去AI痕迹、查重优化,全流程智能辅助,帮你把论文写作变得简单高效,告别熬夜改稿的焦虑&am…...
【小白快速上手】 OpenClaw 安装部署全流程(含安装包)
OpenClaw 一键安装包|一键部署,告别复杂环境配置 适配系统:Windows10/11 64 位当前版本:v2.7.5(虾壳云版)核心优势:全程可视化操作,无需命令行、无需手动配置 Python/Node.js&#…...
FModel完整部署指南:UE5资源提取与逆向解析实战
1. 为什么FModel不是“另一个UE资源查看器”,而是虚幻项目逆向分析的起点FModel虚幻引擎资源提取工具完整部署指南——这标题里藏着三个被多数人忽略的关键信号:“FModel”不是泛指,“虚幻引擎”特指UE4/UE5原生资产体系,“完整部…...
城通网盘直链解析终极指南:3分钟告别广告等待
城通网盘直链解析终极指南:3分钟告别广告等待 【免费下载链接】ctfileGet 获取城通网盘一次性直连地址 项目地址: https://gitcode.com/gh_mirrors/ct/ctfileGet 还在为城通网盘下载而烦恼吗?每次下载都要面对烦人的广告等待,还要输入…...
《Java 100 天进阶之路》第32篇:Java常用工具类(Objects、Collections、Arrays深入)
第32篇:Java常用工具类(Objects、Collections、Arrays深入) 📌 系列导航:《Java 100 天进阶之路》完整目录 | ⬅️ 上一篇:第31篇:Java数组详解 | ➡️ 下一篇:第33篇:Ja…...
Go语言调试技巧:Delve调试器
Go语言调试技巧:Delve调试器 1. Delve使用 dlv debug main.go (dlv) breakpoint main.go:10 (dlv) continue2. 总结 Delve是Go语言的官方调试器,支持断点、单步执行等调试功能。...
别再手动触发ADC了!用STM32CubeMX配置定时器触发+DMA搬运,实现精准采样(附F1/F4差异说明)
STM32CubeMX定时器触发ADCDMA全自动采样实战指南 在嵌入式数据采集系统中,ADC采样的精准度和效率直接影响整个系统的性能表现。传统的手动触发方式不仅占用CPU资源,还难以保证采样间隔的一致性。本文将深入解析如何利用STM32CubeMX配置定时器触发ADC配合…...
