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

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=0i1{max(dp[k][j1],sub(k+1,i))}                               =mink=0i1{max(dp[k][j1],sum(nums[k+1j]))}

  • 确定边界:填表法

        nums = [7,2,5,10,8],m=2。

i\j012
0无法分为0组INT_MAXINT_MAX
1无法分为0组71个数无法分为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 &#xff0c;你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1&#xff1a;输入&#xff1a;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&#xff1a; / -------…...

最新2024届【海康威视】内推码【GTK3B6】

最新2024届【海康威视】内推码【GTK3B6】 【内推码使用方法】 1.请学弟学妹们登录校招官网&#xff0c;选择岗位投递简历&#xff1b; 2.投递过程中填写内推码完成内推步骤&#xff0c;即可获得内推特权。 内推码&#xff1a;GTK3B6 内推码&#xff1a;GTK3B6 内推码&…...

边写代码边学习之LSTM

1. 什么是LSTM 长短期记忆网络 LSTM&#xff08;long short-term memory&#xff09;是 RNN 的一种变体&#xff0c;其核心概念在于细胞状态以及“门”结构。细胞状态相当于信息传输的路径&#xff0c;让信息能在序列连中传递下去。你可以将其看作网络的“记忆”。理论上讲&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. 串口连接开发板&#xff0c;配置nfs5 修改网络文件6 验证nfs 是否成功总结 1. 配置VM虚拟机的桥接网络 右击设置&#xff0c;选择添加网络&#xff0c;按照如下顺序操作…...

【Android】Retrofit2和RxJava2新手快速上手

写这篇博客的目的 网上关于Retrofit2和RxJava2的博客特别多&#xff0c;但是内容特别复杂&#xff0c;一上来就讲解很高级的用法 其实我们没必要像高考做题家一样&#xff0c;把每个API都背的滚瓜烂熟 熟悉基本用法&#xff0c;高阶用法需要的时候再逐个了解就行了 因为博客…...

1.4 Nacos注册中心

目录 什么是Nacos Nacos下载和安装 下载和安装 启动 Nacos服务注册与发现 Nacos的服务分级存储模型 什么是分级存储模型 配置实例集群 配置同集群优先的负载均衡 权重配置 点击编辑按钮 配置所需的权重 环境隔离 创建namespace 什么是Nacos Nacoshttps://nacos.i…...

AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

我写了好多注释&#xff0c;一看就能看懂&#xff0c;这个题目我想了6&#xff0c;7个小时&#xff0c;一开始忽略了船的位置和要把船安置的位置一致的情况&#xff0c;补上就对了。 #include <iostream> using namespace std; int inf 0x3f3f3f3f, num[1007], dp[1007…...

红米电视 ADB 安装 app 报错 failed to authenticate xxx:5555

开启电视开发者模式&#xff0c;允许安装未知来源应用及开启 ADB 调试电脑端下载 adb 工具 点击下载同一局域网的电脑使用 adb 工具连接&#xff08;提前查看电视 IP&#xff09;D:\adb>adb connect 192.168.1.7 * daemon not running; starting now at tcp:5037 * daemon s…...

Linux 下设置开机自启动的方法

文章目录 事先准备对于普通的 Linux对于 RedHat Enterprise Linux 9 笔者的运行环境&#xff1a; 设置成功过的 Linux&#xff1a; RedHat Enterprise Linux 9 x86_64 CentOS 8 x86_64 事先准备 进行这个教程之前&#xff0c;必须要先安装好一个 Linux 操作系统。这个 Linux…...

MySQL常见问题处理(三)

MySQL 常见问题解决 夕阳留恋的不是黄昏&#xff0c;而是朝阳 上一章简单介绍了MySQL数据库安装(二), 如果没有看过, 请观看上一章 一. root 用户密码忘记&#xff0c;进行重置操作 复制内容来源链接: https://blog.csdn.net/weixin_48927364/article/details/123556927 一.…...

maven中常见问题

文章目录 一、配置项提示二、父子打包三、打包之后不显示target四、自定义打包之后的jar包名称五、整个项目打包5.1、父项目管理插件和微服务打包 一、配置项提示 SpringBoot中提示错误信息 表示的是SpringBoot中的注释提示没有配置&#xff01;那么可以来使用一下springboot官…...

vue2中bus的使用

说明&#xff1a;为了解决组件间的通信&#xff0c;也就是组件与组件间的数据传递(它们之间毫无关系)&#xff1b; 这里以组件1传递数据到组件2为例 1.首先新建一个Bus.js文件 import Vue from vue const Bus new Vue() export default Bus 2.在组件1中引用 传递数据 imp…...

实证研究在机器学习中的应用

实证研究是一种基于实际数据和事实的科学研究方法&#xff0c;目的是通过观察、测量、分析和解释数据来验证或否定某个假设、理论或研究问题。这种研究方法通常用于社会科学、自然科学和医学等领域。以下是实证研究的详细解释&#xff1a; 研究目标&#xff1a;实证研究旨在通过…...

IO进程线程day8(2023.8.6)

一、Xmind整理&#xff1a; 管道的原理&#xff1a; 有名管道的特点&#xff1a; 信号的原理&#xff1a; 二、课上练习&#xff1a; 练习1&#xff1a;pipe 功能&#xff1a;创建一个无名管道&#xff0c;同时打开无名管道的读写端 原型&#xff1a; #include <unist…...

【5G NR】逻辑信道、传输信道和物理信道的映射关系

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…...

tmux基础教程

tmux基础教程 Mac安装 brew install tmuxubuntu安装 sudo apt-get install tmux入门使用 会话 (Session) Ctrlb d: 分离当前会话。Ctrlb s: 列出所有会话。Ctrlb $: 重命名当前会话。 窗口&#xff08;Window&#xff09; Ctrlb c: 创建一个新窗口, 状态栏会显示多个窗…...

项目实战 — 消息队列(4){消息持久化}

目录 一、消息存储格式设计 &#x1f345; 1、queue_data.txt&#xff1a;保存消息的内容 &#x1f345; 2、queue_stat.txt&#xff1a;保存消息的统计信息 二、消息序列化 三、自定义异常类 四、创建MessageFileManger类 &#x1f345; 1、约定消息文件所在的目录和文件名…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...