力扣 343. 整数拆分

题目来源:https://leetcode.cn/problems/integer-break/description/

 

C++题解1:动态规划。dp[i] 代表数字i拆分后得到的最大乘积。递归公式为拆分后两个数的最大乘积相乘,即 dp[i] = max(dp[i], dp[j] * dp[i-j])。对于n=2或3需要另外讨论。

class Solution {
public:
    int integerBreak(int n) {
        if(n == 2) return 1;
        else if(n == 3) return 2;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++){
                dp[i] = max(dp[i], dp[j] * dp[i-j]);
            }
        }
        return dp[n];
    }
};

C++题解2(来源代码随想录):动规五部曲。

  1. 确定dp数组(dp table)以及下标的含义。dp[i]:分拆数字i,可以得到的最大乘积为dp[i]。
  2. 确定递推公式。 dp[i]最大乘积是怎么得到的呢?其实可以从1遍历j,然后有两种渠道得到dp[i]。一个是j * (i - j) 直接相乘;另一个是j * dp[i - j],相当于是拆分(i - j),对这个拆分不理解的话,可以回想dp数组的定义。那有同学问了,j怎么就不拆分呢?j是从1开始遍历,拆分j的情况,在遍历j的过程中其实都计算过了。那么从1遍历j,比较(i - j) * j和dp[i - j] * j 取最大的。递推公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));也可以这么理解,j * (i - j) 是单纯的把整数拆分为两个数相乘,而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
  3. dp的初始化。初始化dp[2] = 1。
  4. 确定遍历顺序。先来看看递归公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))。dp[i] 是依靠 dp[i - j]的状态,所以遍历i一定是从前向后遍历,先有dp[i - j]再有dp[i]。
  5. 举例推导dp数组
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

C++题解3(来源代码随想录):贪心算法。“拆分一个数n 使之乘积最大,那么一定是拆分成m个近似相同的子数相乘才是最大的”。每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/55083.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Android 面试题 线程间通信 六

&#x1f525; 主线程向子线程发送消息 Threadhandler&#x1f525; 子线程中定义Handler&#xff0c;Handler定义在哪个线程中&#xff0c;就跟那个线程绑定&#xff0c;在线程中绑定Handler需要调用Looper.prepare(); 方法&#xff0c;主线程中不调用是因为主线程默认帮你调用…

IP 工具

什么是IP 工具 IP 工具是用于轻松扫描和排除网络 IP 地址空间故障的网络工程工具。IP 工具使网络管理员能够审核、跟踪和监视 IP 地址、子网以及使用 IP 的设备和主机的性能。这个全面的网络工程工具集包括高级 IP 工具&#xff0c;如 Ping、系统资源管理器、MAC 地址解析器和…

网格简化(QEM)学习笔记

文章目录 网格简化(QEM)1 概述与原理1.1 网格简化的应用1.2 常见的简化操作1.3 二次误差度量 2 算法流程2.1 逐步分析 3 Python代码实现3.1 测试结果 4 总结参考 网格简化(QEM) 1 概述与原理 网格简化&#xff0c;通过减少复杂网格数据的顶点、边和面的数量简化模型的表达&am…

Java版工程行业管理系统源码-专业的工程管理软件- 工程项目各模块及其功能点清单

&#xfeff; 工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据…

021 - STM32学习笔记 - Fatfs文件系统(三) - 细化与总结

021 - STM32学习笔记 - Fatfs文件系统&#xff08;三&#xff09; - 细化与总结 上节内容中&#xff0c;初步实现了FatFs文件系统的移植&#xff0c;并且实现了设备的挂载、文件打开/关闭与读写功能&#xff0c;这里对上节遗留的一些问题进行总结&#xff0c;并且继续完善文件…

Mybatis插件

文章目录 1. 如何自定义插件1.1 创建接口Interceptor的实现类1.2 配置拦截器1.3 运行程序 2. 插件原理2.1 解析过程2.2 创建代理对象2.2.1 Executor2.2.2 StatementHandler2.2. 3ParameterHandler2.2.4 ResultSetHandler 2.3 执行流程2.4 多拦截器的执行顺序 3. 1. 如何自定义插…

【Redis】内存数据库Redis进阶(Redis持久化)

目录 分布式缓存 Redis 四大问题Redis 持久化RDB (Redis DataBase)RDB执行时机RDB启动方式——save指令save指令相关配置save指令工作原理save配置自动执行 RDB启动方式——bgsave指令bgsave指令相关配置bgsave指令工作原理 RDB三种启动方式对比RDB特殊启动形式RDB优点与缺点 A…

Git全栈体系(三)

第六章 GitHub 操作 一、创建远程仓库 二、远程仓库操作 命令名称作用git remote -v查看当前所有远程地址别名git remote add 别名 远程地址起别名git push 别名 分支推送本地分支上的内容到远程仓库git clone 远程地址将远程仓库的内容克隆到本地git pull 远程库地址别名 远…

基于SpringCloud+Vue的分布式架构网上商城系统设计与实现(源码+LW+部署文档等)

博主介绍&#xff1a; 大家好&#xff0c;我是一名在Java圈混迹十余年的程序员&#xff0c;精通Java编程语言&#xff0c;同时也熟练掌握微信小程序、Python和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…

Spring入门-技术简介、IOC技术、Bean、DI

前言 Spring是一个开源的项目&#xff0c;并不是单单的一个技术&#xff0c;发展至今已形成一种开发生态圈。也就是说我们可以完全使用Spring技术完成整个项目的构建、设计与开发。Spring是一个基于IOC和AOP的架构多层j2ee系统的架构。 SpringFramework&#xff1a;Spring框架…

06-向量的更多术语和表示法

向量 引入的概念&#xff1a;向量就是一组有序的数字, 我们在理解它的时候&#xff0c; 可以把它理解成是一个有效的线段&#xff0c;也可以把它理解成是空间中的一个点&#xff0c;那么与之相对应的一个数字&#xff0c;也就是我们在初等数学中学的一个一个数&#xff0c;我们…

GRNN神经网络原理与matlab实现

1案例背景 1.1GRNN神经网络概述 广义回归神经网络(GRNN Generalized Regression Neural Network&#xff09;是美国学者 Don-ald F. Specht在1991年提出的,它是径向基神经网络的一种。GRNN具有很强的非线性映射能力和柔性网络结构以及高度的容错性和鲁棒性,适用于解决非线性问…

关于综合能源智慧管理系统的架构及模式规划的研究

安科瑞 华楠 摘 要&#xff1a;探讨了国内外能源互联网的研究发展&#xff0c;分析了有关综合智慧能源管理系统的定位&#xff0c;以及系统的主要特点&#xff0c;研究了综合智慧能源管理系统的构架以及模式规划。 关键词&#xff1a;综合能源&#xff1b;智慧管理系统&#…

如何在不使用脚本和插件的情况下手动删除 3Ds Max 中的病毒?

如何加快3D项目的渲染速度&#xff1f; 3D项目渲染慢、渲染卡顿、渲染崩溃&#xff0c;本地硬件配置不够&#xff0c;想要加速渲染&#xff0c;在不增加额外的硬件成本投入的情况下&#xff0c;最好的解决方式是使用渲云云渲染&#xff0c;在云端批量渲染&#xff0c;批量出结…

【PHP代码审计】ctfshow web入门 php特性 93-104

ctfshow web入门 php特性 93-104 web 93web 94web 95web 96web 97web 98web 99web 100web 101web 102web 103web 104 web 93 这段PHP代码是一个简单的源码审计例子&#xff0c;让我们逐步分析它&#xff1a; include("flag.php");: 这行代码将flag.php文件包含进来。…

从零开始学python(十二)如何成为一名优秀的爬虫工程师

前言 回顾之前讲述了python语法编程 必修入门基础和网络编程&#xff0c;多线程/多进程/协程等方面的内容&#xff0c;后续讲到了数据库编程篇MySQL&#xff0c;Redis&#xff0c;MongoDB篇&#xff0c;和机器学习&#xff0c;全栈开发&#xff0c;数据分析前面没看的也不用往…

SSL原理详解

SSL协议结构&#xff1a; SSL协议分为两层&#xff0c;下层为SSL记录协议&#xff0c;上层为SSL握手协议、SSL密码变化协议和SSL警告协议。 1.下层为SSL记录协议&#xff0c;主要作用是为高层协议提供基本的安全服务 建立在可靠的传输之上&#xff0c;负责对上层的数据进行分块…

DeepVO 论文阅读

论文信息 题目&#xff1a;DeepVO Towards End-to-End Visual Odometry with Deep Recurrent Convolutional Neural Networks 作者&#xff1a;Sen Wang, Ronald Clark, Hongkai Wen and Niki Trigoni 代码地址&#xff1a;http://senwang.gitlab.io/DeepVO/ (原作者并没有开源…

【C++】从0到1讲继承|复杂的菱形继承

个人主页&#xff1a;&#x1f35d;在肯德基吃麻辣烫 我的gitee&#xff1a;gitee仓库 分享一句喜欢的话&#xff1a;热烈的火焰&#xff0c;冰封在最沉默的火山深处。 前言 本文主要讲述的是继承的概念&#xff0c;以及基类和派生类和衍生出的各种东西&#xff0c;还有多继承…

前端代码注释率

nodejs差代码注释率 /*** author duan* source https://editor.csdn.net/md/?not_checkout1&spm1011.2124.3001.6192* date 2023-7-7* * 统计指定目录下代码行数及注释率* * 用法: node count.js <路径> [后缀名]...* 后缀名不填的话默认为统计 .js 和 .ts 文件* *…