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

leetcode 343.整数拆分

思路:记忆化搜索或者动态规划

我们首先捋一下思路,而且分析最优解这一类问题,我们需要几个步骤:

1.看问题的描述,找出问题问的最优问题是什么;

2.然后我们就模拟一下这个问题进行到最后一步是什么样子;

3.去掉最后一步又是什么样子;

4.照着2.3步一直类推,这就是递推的过程,也就是我们需要模拟的过程。

举个例子,就拿这道题来说,最优问题是:把一个数拆开k个,使其乘积最大。

进行到最后一步时,是拆出的所有数进行相乘,得出最大乘积;

那么我们去掉最后一步时,其实就是把其中的两个数合起来,这个时候是最后一步的前一步。

这只类推,直到推到所给的n数。

就是这么一个过程。可能有点抽象,那么就先看记忆化搜索的代码,其实也就是DFS:

int mem[100];
class Solution {
public:int dfs(int u){if(mem[u])return mem[u];if(u==0)return 1;else{int res=0;for(int i=1;i<u;i++){res=max(res,max(i*(u-i),dfs(u-i)*i));}return mem[u]=res;}}int integerBreak(int n) {return dfs(n);}
};

好了,剩下的DP其实就是对于上面的这个递推进行了改写而已,dfs改写成dp数组就行了。由于dfs中的u也在变化,其中的拆分数也在变化,所以需要两个循环进行改写。

上代码:


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

相关文章:

leetcode 343.整数拆分

思路&#xff1a;记忆化搜索或者动态规划 我们首先捋一下思路&#xff0c;而且分析最优解这一类问题&#xff0c;我们需要几个步骤&#xff1a; 1.看问题的描述&#xff0c;找出问题问的最优问题是什么&#xff1b; 2.然后我们就模拟一下这个问题进行到最后一步是什么样子&a…...

部署Zabbix Agents添加使能监测服务器_Linux平台_Yum源/Archive多模式

Linux平台 一、从yum源脚本安装部署Zabbix-Agent,添加Linux Servers/PC 概述 Zabbix 主要有以下几个组件组成: Zabbix Server:Zabbix 服务端,Zabbix的核心组件,它负责接收监控数据并触发告警,还负责将监控数据持久化到数据库中。 Zabbix Agent:Zabbix客户端,部署在被监…...

吴恩达2022机器学习专项课程(一) 第一周课程实验:模型表示(Lab_03)

目标 学习如何使用一个变量实现线性回归模型。 导入需要的库 存储特征x和目标变量y 这是真实的训练集&#xff0c;[1.0,2.0]是房子的大小&#xff0c;[300,500]是房子的价格。 使用数组存储训练集的数据&#xff1a; x_train&#xff1a;存储的是所有特征&#xff0c;[1.…...

流畅的 Python 第二版(GPT 重译)(十)

第十八章&#xff1a;with、match 和 else 块 上下文管理器可能几乎与子例程本身一样重要。我们只是初步了解了它们。[…] Basic 有一个 with 语句&#xff0c;在许多语言中都有 with 语句。但它们的功能不同&#xff0c;它们都只是做一些非常浅显的事情&#xff0c;它们可以避…...

【自然语言处理七-经典论文-attention is all you need】

然语言处理七-经典论文-attention is all you need 摘要原文译文小结 1&#xff1a;引言原文译文小结 2&#xff1a;背景原文译文小结 3&#xff1a;模型架构原文译文小结 3.1 编码器和解码器原文译文小结 3.2 注意力原文译文小结3.2.1 缩放点积注意力原文总结 3.2.2 多头注意力…...

【嵌入式】STM32和I2C通信

一、简介 I2C(Inter IC Bus)是有飞利浦公司开发的一种通用数据总线&#xff0c;主要通过两个通信线SCL和SDA进行通信&#xff0c;其中SCL(Serial Clock)是时钟线&#xff0c;用于收发双方同步数据&#xff0c;SDA(Serial Data)是数据线&#xff0c;用于传输数据。是一种同步半…...

如何使用Harmony OS控制外设——输入输出?

相关知识点 Hi3861开发板第一个示例程序演示 熟悉使用DevEco Device Tool插件进行程序烧录 熟悉串口调试工具sscom的使用 官方文档中控制核心板上LED的led_example.c讲解及演示 源码路径&#xff1a;applications/sample/wifi-iot/app/iothardware/led_example.cHarmony OS …...

1.1-数组-704. 二分查找★

704. 二分查找 ★ 力扣题目链接&#xff0c;给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;搜索 nums 中的 target&#xff0c;如果存在返回下标&#xff0c;否则返回 -1。n 将在 [1, 10000]之间。 可以假设 nums 中的所…...

人物百度百科怎么做?需要什么资料?

在互联网时代&#xff0c;百度百科作为国内最具权威性的知识分享平台&#xff0c;吸引了大量用户关注和参与。究竟哪些人适合创建和编辑人物百度百科呢&#xff1f;本文伯乐网络传媒将为您揭秘人物百度百科的适用人群&#xff0c;并详细介绍如何注册、登录、创建及维护人物百度…...

在基于Android相机预览的CV应用程序中使用 OpenCL

查看&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;OpenCV4.9.0在Android 开发简介 下一篇&#xff1a;在 MacOS 中安装 本指南旨在帮助您在基于 Android 相机预览的 CV 应用程序中使用 OpenCL ™。教程是为 Android Studio 20…...

网络分类简述与数据链路层协议(PPP)

实验拓扑 实验要求 1、R1和R2使用PPP链路直连&#xff0c;R2和R3把2条PPP链路捆绑为PPP MP直连按照图示配置IP地址 2、R2对R1的PPP进行单向chap验证 3、R2和R3的PPP进行双向chap验证 实验思路 给R1、R2的S3/0/0接口配置IP地址&#xff0c;已给出网段192.168.1.0/24R2作为主…...

Linux文件系列:磁盘,文件系统,软硬链接

Linux文件系列:磁盘,文件系统,软硬链接 一.磁盘相关知识1.磁盘机械构成2.磁盘物理存储3.磁盘逻辑存储1.LBA地址2.磁盘的分区和分组 二.文件系统和inode1.inode结构体2.文件系统1.Super Block(超级块)2.Group Descriptor Table(块组描述表GDT)3.inode Table4.Data Blocks5.Block…...

GPT4.0

GPT4.0 支持官网所有功能以及所有第三方GPTS&#xff0c;完全同步官网。无需魔法&#xff0c;填写授权码直达官网。全天超18小时维护&#xff0c;无需担心不稳定。没有永久卡&#xff0c;3.5免费提供&#xff0c;4.0可以按需下单即可&#xff0c;不存在跑路。 需要的联系...

软件工程(双语)

教材《软件工程 实践者的研究方法》 双语教学&#xff0c;但目前感觉都是在讲没用的 ”过程决定质量&#xff0c;复用决定效率” 介绍 软工的本质 程序数据结构算法 软件程序文档&#xff08;需求、模型、说明书&#xff09; 软件应用&#xff1a; 系统软件 应用 工程/科学…...

网络——套接字编程UDP

目录 端口号 源端口号和目的端口号 认识TCP协议和UDP协议 网络字节序 socket编程接口 socket常见接口 sockaddr结构 UDP socket bind recvfrom sendto 编写客户端 绑定INADDR_ANY 实现聊天功能 端口号 在这之前我们已经说过源IP地址和目的IP地址&#xff0c;还有…...

FPGA_AD9361

1.集成12位DAC和ADC的一款器件&#xff0c;2个输入模拟通道和2个输出模拟通道 2.• TX频段&#xff1a;47 MHz至6.0 GHz • RX频段&#xff1a;70 MHz至6.0 GHz 3.SPI配置成LVDS或CMOS接口&#xff0c;也可以还可以选择FDD&#xff08;频分双工——全双工&#xff0c;操作时需…...

探讨Java代码混淆加固工具

摘要 本篇博客将介绍几种常用的Java代码混淆工具&#xff0c;如ProGuard、Allatori Java Obfuscator、VirboxProtector、ipaguard和DashO。我们将深入探讨它们的特点、功能以及在保护Java应用程序安全方面的作用。此外&#xff0c;还将强调在使用Java代码混淆工具时需要注意的安…...

Linux——du, df命令查看磁盘空间使用情况

一、实现原理&#xff1a; df 命令的全称是Disk Free &#xff0c;显而易见它是统计磁盘中空闲的空间&#xff0c;也即空闲的磁盘块数。它是通过文件系统磁盘块分配图进行计算出的。 du 命令的全称是 Disk Used &#xff0c;统计磁盘有已经使用的空间。它是直接统计各文件各目…...

数据库实验(一)SQL Server触发器

目录 触发器的定义 触发器和存储过程的区别 触发器的优点 触发器的作用 触发器的分类 DML触发器 DDL触发器 登录触发器 触发器的工作原理 inserted表 deleted表 创建触发器 编程要求 测试要求&#xff1a; 实验代码&#xff1a; 触发器的定义 触发器是建立在触…...

添加网址到主页

基于localStorage的网址收藏夹-CSDN博客 为了通过安卓菜单添加网址到主页中&#xff0c;调试了几个小时&#xff0c;主要踩了几个坑。 1.localStorage 通过域名隔离&#xff0c;需要加载主页才能读写。 2.WebView 可以不显示&#xff0c;但是 JS 代码要放在 window.onload 中…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...