leetcode 343. 整数拆分

2023.8.10

       本题用dp算法来做,dp[i]代表的含义是:当前数字i 在拆分之后所能获得的最大乘积。然后由于n>=2,所以dp[0]和dp[1]没有意义,不用初始化,直接初始化dp[2]= 1。  然后再遍历给dp数组赋值:dp[i]的来源有两个:①将i拆成 j 和 (i - j) ,然后相乘,即j*(i-j)。 ② 将i 拆成 j 和(i-j), 然后(i-j)的最大拆分乘积为dp[i-j],即 j * dp[i-j]。 

        思考画的草图:

        代码如下: 

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1); //dp[i]的含义是:当前数字i拆分之后的最大乘积值。
        dp[2] = 1; //初始化
        //遍历赋值
        for(int i=3; i<=n; i++)
        {
            for(int j=1; j<=i/2; j++)
            {
                dp[i] = max(dp[i] , max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

 

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

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

相关文章

业务逻辑漏洞之支付逻辑漏洞

业务逻辑漏洞之支付逻辑漏洞 一、漏洞挖掘介绍二、Web漏洞产生的原因三、业务逻辑简述四、 常见业务逻辑漏洞的功能点五、支付逻辑漏洞5.1、漏洞背景5.2、产生原因5.3、测试方法 六、挖到这些漏洞有什么用&#xff1f; 一、漏洞挖掘介绍 漏洞定义&#xff1a; 官方定义&#…

Linux基础与拓展

文章目录 虚拟机网络连接方式VIMvi和vim常用的三种模式各种模式的相互切换快捷键 用户管理权限 基本介绍&#xff1a;添加用户指定/修改密码删除用户切换用户用户组 路径命令学习mkdir命令介绍语法注意 touch 创建文件介绍语法 cat 查看文件内容介绍语法 more 查看文件内容介绍…

pve和openwrt以及我的电脑中网络的关系和互通组网

情况1 一台主机 有4个口&#xff0c;分别eth0,eth1,eth2,eth3 pve有管理口 这个情况下 &#xff0c;没有openwrt 直接电脑和pve管理口连在一起就能进pve管理界面 情况2 假设pve 的管理口味eth0 openwrt中桥接的是eth0 eth1 eth2 那么电脑连接eth3或者pve管理口设置eth3&#xf…

mysql不用窗口函数,后面加一列序号

前言 在后端开发中最常用的数据库还是比较稳定的5.8&#xff0c;而窗口函数是只有在mysql8以上才有的&#xff0c;然后在开发中有个需要排序序号的需求&#xff0c;翻找资料&#xff0c;问AI得出结论可以实现。 列出方法 如果你使用的是MySQL 5.7版本&#xff0c;而没有窗口…

C++笔记之回调函数的演变

C笔记之回调函数的演变 code review! 文章目录 C笔记之回调函数的演变1.使用函数指针2.使用typedef加函数指针3.使用std::using加函数指针4.使用typedef加std::function5.使用std::using加std::function6.使用回调和不使用回调对比 1.使用函数指针 代码 #include <iostre…

C# WPF 开源主题 HandyControl 的使用(一)

HandyControl是一套WPF控件库&#xff0c;它几乎重写了所有原生样式&#xff0c;同时包含80余款自定义控件&#xff08;正逐步增加&#xff09;&#xff0c;下面我们开始使用。 1、准备 1.1 创建项目 C# WPF应用(.NET Framework)创建项目 1.2 添加包 1.3 在App.xaml中引用…

性能调优,看过的都说会了...

在展开今天的内容之前&#xff0c;我们先来看一下&#xff0c;是不是任何一个测试都可以学习性能测试。 如果说需求、开发、DB、运维、测试是单一一门学科&#xff0c;那么性能就是综合学科&#xff0c;它包含了需求分析、DB、开发、测试、运维的所有学科。 所以说&#xff0…

html实现商品图片放大镜,html图片放大镜预览

效果 实现 复制粘贴&#xff0c;修改图片路径即可使用 <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>商品图片放大镜</title></head><style>body {margin: 0;padding: 0;}#app {padding: 10px;posit…

Java反射机制详解与使用方法大全!!!

❤ 作者主页&#xff1a;李奕赫揍小邰的博客 ❀ 个人介绍&#xff1a;大家好&#xff0c;我是李奕赫&#xff01;(&#xffe3;▽&#xffe3;)~* &#x1f34a; 记得点赞、收藏、评论⭐️⭐️⭐️ &#x1f4e3; 认真学习!!!&#x1f389;&#x1f389; 文章目录 Java反射机制…

c++中的继承

文章目录 1.继承的概念及定义1.1继承的概念1.2继承的定义1.2.1定义格式1.2.2继承关系和访问限定符1.2.3继承基类成员访问方式的变化 2.基类和派生类对象赋值转换3.继承中的作用域4.派生类的默认成员函数5.继承与友元6.继承与静态成员7.复杂的菱形继承及菱形虚拟继承 1.继承的概…

【深度学习注意力机制系列】—— SKNet注意力机制(附pytorch实现)

SKNet&#xff08;Selective Kernel Network&#xff09;是一种用于图像分类和目标检测任务的深度神经网络架构&#xff0c;其核心创新是引入了选择性的多尺度卷积核&#xff08;Selective Kernel&#xff09;以及一种新颖的注意力机制&#xff0c;从而在不增加网络复杂性的情况…

opencv基础53-图像轮廓06-判断像素点与轮廓的关系(轮廓内,轮廓上,轮廓外)cv2.pointPolygonTest()

点到轮廓的距离 在 OpenCV 中&#xff0c;函数 cv2.pointPolygonTest()被用来计算点到多边形&#xff08;轮廓&#xff09;的最短距离&#xff08;也 就是垂线距离&#xff09;&#xff0c;这个计算过程又称点和多边形的关系测试。该函数的语法格式为&#xff1a; retval cv2…

Linux —— 基础I/O

一&#xff0c;背景介绍 狭义的文件存放在磁盘上&#xff0c;广义上在Linux下一切皆文件&#xff1b;磁盘上的文件一般为永久存储的外设&#xff0c;本质上对文件的操作&#xff0c;即为对外设的输入和输出&#xff08;简称I/O&#xff09;&#xff1b;空文件并不是不占磁盘文件…

uC-OS2 V2.93 STM32L476 移植:串口打印篇

前言 前几篇已经 通过 STM32CubeMX 搭建了 NUCLEO-L476RG 的 STM32L476RG 的 裸机工程&#xff0c;下载了 uC-OS2 V2.93 的源码&#xff0c;并把 uC-OS2 的源文件加入 Keil MDK5 工程&#xff0c;通过适配 Systick 系统定时器与 PendSV 实现任务调度&#xff0c;初步让 uC-OS2 …

Facebook商城号最全解析,Facebook Marketplace运营技巧

相信许多做跨境的小伙伴都听说过Facebook商城号。其实所谓的商城并不是Facebook Shop&#xff0c;而是指Facebook Marketplace&#xff0c;它不像前者需要各类入驻条件&#xff0c;只要拥有facebook账号而且所在地区有能够使用marketplace就可以在上面进行商品售卖。这种低成本…

validator入门

validator中文文档地址和英文地址 https://docs.jboss.org/hibernate/validator/4.2/reference/zh-CN/html/validator-gettingstarted.html https://docs.jboss.org/hibernate/validator/6.0/reference/en-US/html_single/#preface自定义hibernate-validator校验 工具类Valid…

设计模式(4)装饰模式

一、介绍&#xff1a; 1、应用场景&#xff1a;把所需的功能按正确的顺序串联起来进行控制。动态地给一个对象添加一些额外的职责&#xff0c;就增加功能来说&#xff0c;装饰模式比生成子类更加灵活。 当需要给一个现有类添加附加职责&#xff0c;而又不能采用生成子类的方法…

谷歌关闭跨域限制.(生成一个开发浏览器),Chrome关闭跨域

(一)、首先找到浏览器在电脑磁盘中的位置,并复制 (二)、复制一个浏览器的快捷方式到桌面(不影响正常浏览器) (三)、chrom鼠标右键属性&#xff0c;修改快捷方式的目标 &#xff08;四&#xff09;chrome.exe 后面添加 --disable-web-security --user-data-dir 复制的Chrome浏览…

力扣hot100刷题记录

二刷hot100&#xff0c;坚持每天打卡&#xff01;&#xff01;&#xff01;Today&#xff1a;2023-8-10 1. 两数之和 // 先求差&#xff0c;再查哈希表 public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map new HashMap<>();for(int i 0;i&…

窥探系列之Mybatis-plus XML分页查询

mybatisPlus分页查总数 Page类在mybatisPlus中用于分页查询&#xff0c;继承Pagination类&#xff0c;Pagination类的searchCount字段控制是否查询总记录数 顺着看哪里用到了searchCount&#xff1a; com.baomidou.mybatisplus.plugins.PaginationInterceptor 是mybatisPlus…