leetcode410. 分割数组的最大值 动态规划
-
hard:https://leetcode.cn/problems/split-array-largest-sum/
-
给定一个非负整数数组 nums 和一个整数 m ,
你需要将这个数组分成 m 个非空的连续子数组。 -
设计一个算法使得这
m 个子数组各自和的最大值最小。
示例 1:输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:输入:nums = [1,2,3,4,5], m = 2
输出:9
示例 3:输入:nums = [1,4,4], m = 3
输出:4提示:1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
题解
-
令 dp[i][j]表示将数组的
前 i 个数分割为 j 组所能得到的最大连续子数组和的最小值 -
确定装填转移方程(考虑dp[i][j]需要遍历所有分为j-1组的情况):
d p [ i ] [ j ] = m i n k = 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u b ( k + 1 , i ) ) } = m i n k = 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u m ( n u m s [ k + 1 … j ] ) ) } dp[i][j]= min_{k=0}^{ i−1} \{max(dp[k][j−1],sub(k+1,i))\}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = min_{k=0}^{ i−1} \{max(dp[k][j−1],sum(nums[k+1…j]))\} dp[i][j]=mink=0i−1{max(dp[k][j−1],sub(k+1,i))} =mink=0i−1{max(dp[k][j−1],sum(nums[k+1…j]))} -
确定边界:填表法
nums = [7,2,5,10,8],m=2。
| i\j | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 无法分为0组 | INT_MAX | INT_MAX |
| 1 | 无法分为0组 | 7 | 1个数无法分为2组(i<j) |
| 2 | 无法分为0组 | 7+2 | m i n ( [ 7 ] , [ 2 ] ) = 2 min([7],[2])=2 min([7],[2])=2 |
| 3 | 无法分为0组 | 7+2+5 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 ] ) ] = 7 min\begin{bmatrix} max(dp[1][1],[2,5]) \\ max(dp[2][1],[5]) \end{bmatrix}=7 min[max(dp[1][1],[2,5])max(dp[2][1],[5])]=7 |
| 4 | 无法分为0组 | 7+2+5+10 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 ] ) ] = 14 min\begin{bmatrix} max(dp[1][1],[2,5,10]) \\ max(dp[2][1],[5,10]) \\ max(dp[3][1],[10]) \end{bmatrix}=14 min max(dp[1][1],[2,5,10])max(dp[2][1],[5,10])max(dp[3][1],[10]) =14 前*个数分为一组和剩下的部分 |
| 5 | 无法分为0组 | 7+2+5+10+8 | m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 , 8 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 , 8 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 , 8 ] ) m a x ( d p [ 4 ] [ 1 ] , [ 8 ] ) ] = 18 min\begin{bmatrix} max(dp[1][1],[2,5,10,8]) \\ max(dp[2][1],[5,10,8]) \\ max(dp[3][1],[10,8])\\ max(dp[4][1],[8]) \end{bmatrix}=18 min max(dp[1][1],[2,5,10,8])max(dp[2][1],[5,10,8])max(dp[3][1],[10,8])max(dp[4][1],[8]) =18 |
code
class Solution {
public:int splitArray(vector<int>& nums, int m) {int n = nums.size();vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, LLONG_MAX));vector<long long> sub(n + 1, 0);for (int i = 0; i < n; i++) {sub[i + 1] = sub[i] + nums[i];}dp[0][0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= min(i, m); j++) {for (int k = 0; k < i; k++) {dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]));}}}return (int)dp[n][m];}
};相关文章:
leetcode410. 分割数组的最大值 动态规划
hard:https://leetcode.cn/problems/split-array-largest-sum/ 给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1:输入:nums [7,2,5,1…...
C函数指针与类型定义
#include <stdio.h> #define PI 3.14 typedef int uint32_t; /* pfun is a pointer and its type is void (*)(void) */ void (*pfun)(void); /* afer typedef like this we can use “pfun1” as a data type to a function that has form like: / -------…...
最新2024届【海康威视】内推码【GTK3B6】
最新2024届【海康威视】内推码【GTK3B6】 【内推码使用方法】 1.请学弟学妹们登录校招官网,选择岗位投递简历; 2.投递过程中填写内推码完成内推步骤,即可获得内推特权。 内推码:GTK3B6 内推码:GTK3B6 内推码&…...
边写代码边学习之LSTM
1. 什么是LSTM 长短期记忆网络 LSTM(long short-term memory)是 RNN 的一种变体,其核心概念在于细胞状态以及“门”结构。细胞状态相当于信息传输的路径,让信息能在序列连中传递下去。你可以将其看作网络的“记忆”。理论上讲&a…...
Elasticsearch8.8.0 SpringBoot实战操作各种案例(索引操作、聚合、复杂查询、嵌套等)
Elasticsearch8.8.0 全网最新版教程 从入门到精通 通俗易懂 配置项目 引入依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.16</version></dependency><dependency>&l…...
《MySQL高级篇》十五、其他数据库日志
文章目录 1. MySQL支持的日志1.1 日志类型1.2 日志的弊端 2. 慢查询日志(slow query log)3. 通用查询日志3.1 问题场景3.2 查看当前状态3.3 启动日志3.4 查看日志3.5 停止日志3.6 删除\刷新日志 4. 错误日志(error log)4.1 启动日志4.2 查看日志4.3 删除\刷新日志4.4 MySQL8.0新…...
【Linux】【预】配置虚拟机的桥接网卡+nfs
【Linux】【预】配置虚拟机的桥接网卡 1. 配置VM虚拟机的桥接网络2 配置Win10中的设置3.配置Linux中的IP4. 串口连接开发板,配置nfs5 修改网络文件6 验证nfs 是否成功总结 1. 配置VM虚拟机的桥接网络 右击设置,选择添加网络,按照如下顺序操作…...
【Android】Retrofit2和RxJava2新手快速上手
写这篇博客的目的 网上关于Retrofit2和RxJava2的博客特别多,但是内容特别复杂,一上来就讲解很高级的用法 其实我们没必要像高考做题家一样,把每个API都背的滚瓜烂熟 熟悉基本用法,高阶用法需要的时候再逐个了解就行了 因为博客…...
1.4 Nacos注册中心
目录 什么是Nacos Nacos下载和安装 下载和安装 启动 Nacos服务注册与发现 Nacos的服务分级存储模型 什么是分级存储模型 配置实例集群 配置同集群优先的负载均衡 权重配置 点击编辑按钮 配置所需的权重 环境隔离 创建namespace 什么是Nacos Nacoshttps://nacos.i…...
AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维
我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。 #include <iostream> using namespace std; int inf 0x3f3f3f3f, num[1007], dp[1007…...
红米电视 ADB 安装 app 报错 failed to authenticate xxx:5555
开启电视开发者模式,允许安装未知来源应用及开启 ADB 调试电脑端下载 adb 工具 点击下载同一局域网的电脑使用 adb 工具连接(提前查看电视 IP)D:\adb>adb connect 192.168.1.7 * daemon not running; starting now at tcp:5037 * daemon s…...
Linux 下设置开机自启动的方法
文章目录 事先准备对于普通的 Linux对于 RedHat Enterprise Linux 9 笔者的运行环境: 设置成功过的 Linux: RedHat Enterprise Linux 9 x86_64 CentOS 8 x86_64 事先准备 进行这个教程之前,必须要先安装好一个 Linux 操作系统。这个 Linux…...
MySQL常见问题处理(三)
MySQL 常见问题解决 夕阳留恋的不是黄昏,而是朝阳 上一章简单介绍了MySQL数据库安装(二), 如果没有看过, 请观看上一章 一. root 用户密码忘记,进行重置操作 复制内容来源链接: https://blog.csdn.net/weixin_48927364/article/details/123556927 一.…...
maven中常见问题
文章目录 一、配置项提示二、父子打包三、打包之后不显示target四、自定义打包之后的jar包名称五、整个项目打包5.1、父项目管理插件和微服务打包 一、配置项提示 SpringBoot中提示错误信息 表示的是SpringBoot中的注释提示没有配置!那么可以来使用一下springboot官…...
vue2中bus的使用
说明:为了解决组件间的通信,也就是组件与组件间的数据传递(它们之间毫无关系); 这里以组件1传递数据到组件2为例 1.首先新建一个Bus.js文件 import Vue from vue const Bus new Vue() export default Bus 2.在组件1中引用 传递数据 imp…...
实证研究在机器学习中的应用
实证研究是一种基于实际数据和事实的科学研究方法,目的是通过观察、测量、分析和解释数据来验证或否定某个假设、理论或研究问题。这种研究方法通常用于社会科学、自然科学和医学等领域。以下是实证研究的详细解释: 研究目标:实证研究旨在通过…...
IO进程线程day8(2023.8.6)
一、Xmind整理: 管道的原理: 有名管道的特点: 信号的原理: 二、课上练习: 练习1:pipe 功能:创建一个无名管道,同时打开无名管道的读写端 原型: #include <unist…...
【5G NR】逻辑信道、传输信道和物理信道的映射关系
博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…...
tmux基础教程
tmux基础教程 Mac安装 brew install tmuxubuntu安装 sudo apt-get install tmux入门使用 会话 (Session) Ctrlb d: 分离当前会话。Ctrlb s: 列出所有会话。Ctrlb $: 重命名当前会话。 窗口(Window) Ctrlb c: 创建一个新窗口, 状态栏会显示多个窗…...
项目实战 — 消息队列(4){消息持久化}
目录 一、消息存储格式设计 🍅 1、queue_data.txt:保存消息的内容 🍅 2、queue_stat.txt:保存消息的统计信息 二、消息序列化 三、自定义异常类 四、创建MessageFileManger类 🍅 1、约定消息文件所在的目录和文件名…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
