按照某种形式分割数组以获得最值
希望看了本文对你有所帮助,参考其他题解写成,取其精华,做以笔记,如有描述不清楚或者错误麻烦指正,不胜感激,不喜勿喷!
最大平均值的和分组【LC813】
You are given an integer array
nums
and an integerk
. You can partition the array into at mostk
non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.Note that the partition must use every integer in
nums
, and that the score is not necessarily an integer.Return the maximum score you can achieve of all the possible partitions. Answers within
10-6
of the actual answer will be accepted.
给定数组
nums
和一个整数k
。我们将给定的数组nums
分成 最多k
个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。注意我们必须使用
nums
数组中的每一个数进行分组,并且分数不一定需要是整数。返回我们所能得到的最大 分数 是多少。答案误差在
10-6
内被视为是正确的。
- 思路:将 n 个元素划分为k个连续子数组,最大化子数组的平均值之和。
-
确定dp数组(dp table)以及下标的含义
dp[i][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数
-
确定递推公式
当 j ≤ k j\le k j≤k时,nums[i]有两种选择,自成一组,或者并入前一组
-
自成一组: d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + n u m [ i ] dp[i][j] = dp[i-1][j-1] + num[i] dp[i][j]=dp[i−1][j−1]+num[i]
-
并入前一组:对于每个nums[i],需要枚举前一组所有可能的初始位置,为了方便计算平均值,使用preSum数组计算前缀和,由于每个子数组至少包含一个元素,因此 s t a r t ∈ [ 1 , i ) start\in[1,i) start∈[1,i)
d p [ i ] [ j ] = d p [ s t a r t − 1 ] [ j − 1 ] + a v e ( n u m s [ s t a r t , i ] ) dp[i][j]=dp[start-1][j-1] + ave(nums[start,i]) dp[i][j]=dp[start−1][j−1]+ave(nums[start,i])
-
以上两个公式可合并为一个:当 s t a r t = i start=i start=i时,新的一组只有 n u m s [ i ] nums[i] nums[i]一个元素
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ s t a r t − 1 ] [ j − 1 ] + a v e ( n u m s [ s t a r t , i ] ) ) dp[i][j] = max(dp[i][j],dp[start-1][j-1]+ave(nums[start,i])) dp[i][j]=max(dp[i][j],dp[start−1][j−1]+ave(nums[start,i]))s t a r t ∈ [ 1 , i ] start\in[1,i] start∈[1,i]
-
p r e S u m [ i ] preSum[i] preSum[i]为前 i − 1 i-1 i−1个数组元素之和,因此连续子数组 n u m s [ s t a r t , i ] nums[start,i] nums[start,i]的平均值可表示为
a v e = ( p r e S u m [ i + 1 ] − p r e S u m [ s t a r t − 1 ] ) / ( i − s t a r t + 1 ) ave=(preSum[i+1] - preSum[start-1])/(i-start+1) ave=(preSum[i+1]−preSum[start−1])/(i−start+1)
-
-
dp数组如何初始化
特殊处理只分为一组时的dp[i][1]
- d p [ 0 ] [ 1 ] = n u m s [ 0 ] dp[0][1] = nums[0] dp[0][1]=nums[0]
- d p [ 1 ] [ 1 ] = ( n u m s [ 0 ] + n u m s [ 1 ] ) / 2 dp[1][1] = (nums[0] + nums[1])/2 dp[1][1]=(nums[0]+nums[1])/2
- d p [ i ] [ 1 ] = ( n u m s [ 0 ] + n u m s [ 1 ] + … … + n u m s [ i ] ) / ( i + 1 ) = p r e S u m [ i + 1 ] / ( i + 1 ) dp[i][1] = (nums[0] + nums[1] + ……+nums[i])/(i+1) = preSum[i+1]/(i+1) dp[i][1]=(nums[0]+nums[1]+……+nums[i])/(i+1)=preSum[i+1]/(i+1)
-
确定遍历顺序
由dp公式可知,外层正序遍历i,内层正序遍历子数组个数j,最后遍历第j个子数组的可能的起始位置start
-
举例推导dp数组
-
代码 :
- 下标均从1开始遍历,代码较清晰
- dp[i+1][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数
- preSum[i+1]对应前i个nums
- 只有数组元素大于等于j时才有可能划分为j个连续子数组
class Solution { public double largestSumOfAverages(int[] nums, int k) { int len = nums.length; double[][] dp = new double[len + 1][k + 1]; double[] preSum = new double[len + 1]; for (int i = 1; i <= len; i++){ preSum[i] = preSum[i-1] + nums[i-1]; } for (int i = 1; i <= len; i++){ dp[i][1] = preSum[i] / i; } for (int i = 1; i <= len; i++){ for (int j = 2; j <= k && j <= i; j++){ // 自成一组 与start = i 合并 // dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + nums[i-1]); // 并入前一组nums[start,i] for (int start = 2; start <= i; start++){ double ave = (preSum[i] - preSum[start - 1]) / (i - start + 1); dp[i][j] = Math.max(dp[i][j],dp[start - 1][j - 1] + ave); } } } return dp[len][k]; } }
-
复杂度
- 时间复杂度: O ( n 2 ∗ k ) O(n^2*k) O(n2∗k)
- 空间复杂度: O ( n ∗ k ) O(n*k) O(n∗k)
- 下标均从1开始遍历,代码较清晰
-
代码:很丑
dp[i][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数
class Solution { public double largestSumOfAverages(int[] nums, int k) { int len = nums.length; double[][] dp = new double[len][k + 1]; double[] preSum = new double[len + 1]; for (int i = 0; i < len; i++){ preSum[i+1] = preSum[i] + nums[i]; } for (int i = 0; i < len; i++){ dp[i][1] = preSum[i + 1] / (i+1); } for (int i = 0; i < len; i++){ for (int j = 2; j <= k && j <= i + 1; j++){ // 自成一组 与start = i 合并 // dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + nums[i-1]); // 并入前一组nums[start,i] for (int start = 1; start <= i; start++){ double ave = (preSum[i + 1] - preSum[start]) / (i - start + 1); dp[i][j] = Math.max(dp[i][j],dp[start - 1][j - 1] + ave); } } } return dp[len - 1][k]; } }
分隔数组以得到最大和【LC1043】
给你一个整数数组
arr
,请你将该数组分隔为长度 最多 为 k 的一些(连续)子数组。分隔完成后,每个子数组的中的所有值都会变为该子数组中的最大值。返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。
-
思路
使用动态规划,将前 i i i个元素进行分割的最大和,可以枚举分割点由之前的状态转移得到,因此可以定义状态 d p [ i + 1 ] dp[i+1] dp[i+1]为将前 i i i个元素分隔变换后能够得到的元素最大和
-
明确
dp
函数/数组的定义。定义状态 d p [ i + 1 ] dp[i+1] dp[i+1]为将前 i i i个元素分隔变换后能够得到的元素最大和
-
确定 base case,初始状态的值: d p [ 0 ] = 0 dp[0]=0 dp[0]=0
-
确定「状态」,也就是原问题和子问题中会变化的变量。
本题中状态为分隔变换后能够得到的元素最大和
-
确定「选择」,也就是导致「状态」产生变化的行为。
第 i i i个元素最长可以分割的子数组为 n u m s [ i − k + 1 : i ] nums[i-k+1:i] nums[i−k+1:i],因此可以枚举与 n u m s [ i ] nums[i] nums[i]为一组的左端点 j ∈ [ i − k + 1 , i ] j \in [i-k+1,i] j∈[i−k+1,i],此时的最大和为将 n u m s [ 0 : j − 1 ] nums[0:j-1] nums[0:j−1]进行分割的最大值与 n u m s [ j : i ] nums[j:i] nums[j:i]变换后的值之和
。实现时,使用变量记录当前子数组 n u m s [ j : i ] nums[j:i] nums[j:i]中元素的最大值 m x mx mx,于是可以得到状态转移方程
d p [ i + 1 ] = m a x j = i i − k + 1 ( d p [ j ] + m x ∗ ( i − j + 1 ) ) dp[i+1]=max_{j=i}^{i-k+1}(dp[j]+mx*(i-j+1)) dp[i+1]=maxj=ii−k+1(dp[j]+mx∗(i−j+1))
-
-
实现
class Solution { public int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n + 1]; for (int i = 0; i < n; i++){ int mx = arr[i]; for (int j = i; j >= Math.max(0, i - k + 1); j--){ mx = Math.max(mx, arr[j]); dp[i + 1] = Math.max(dp[i + 1], dp[j] + mx * (i - j + 1)); } } return dp[n]; } }
-
复杂度
- 时间复杂度: O ( n k ) O(nk) O(nk)
- 空间复杂度: O ( n 2 ) O(n^2) O(n2)
-
填充书架【LC1105】
给定一个数组
books
,其中books[i] = [thicknessi, heighti]
表示第i
本书的厚度和高度。你也会得到一个整数shelfWidth
。按顺序 将这些书摆放到总宽度为
shelfWidth
的书架上。先选几本书放在书架上(它们的厚度之和小于等于书架的宽度
shelfWidth
),然后再建一层书架。重复这个过程,直到把所有的书都放在书架上。需要注意的是,在上述过程的每个步骤中,摆放书的顺序与你整理好的顺序相同。
- 例如,如果这里有 5 本书,那么可能的一种摆放情况是:第一和第二本书放在第一层书架上,第三本书放在第二层书架上,第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高,书架整体的高度为各层高之和。
以这种方式布置书架,返回书架整体可能的最小高度。
dfs+记忆化:选或不选
-
思路:
感觉递推的形式不是很好写,所以一开始的想法是dfs+记忆化。每遇到一本书,我们可以选择新建一层放置这本书,也可以选择在上一次继续放置这本书,影响结果的有两个因素:该层已经摆放的书的宽度以及最大高度。因此在dfs过程需要记录这两个值,定义 d f s ( i , w i d t h , m a x H e i g h t ) dfs(i,width,maxHeight) dfs(i,width,maxHeight)为上一层已经摆放的书的宽度为 w i d t h width width,并且最大高度为 m a x H e i g h t maxHeight maxHeight时,摆放第 i i i本书及剩下的书全部摆放完毕需要的最小高度。那么 d f s ( 0 , 0 , 0 ) dfs(0,0,0) dfs(0,0,0)即为最终答案
-
实现:选或不选
class Solution { int[][] dp; int[][] books; int shelfWidth; public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; dp = new int[n + 1][shelfWidth + 1]; this.books = books; this.shelfWidth = shelfWidth; return dfs(0, 0, 0); } public int dfs(int i, int width, int maxHeight){ if (i == books.length) return maxHeight; if (dp[i][width] != 0) return dp[i][width]; // 新建一层 int res = maxHeight + dfs(i + 1, books[i][0], books[i][1]); // 如果宽度满足要求 那么可以继续往后面放 if (width + books[i][0] <= shelfWidth){ res = Math.min(res, dfs(i + 1, width +books[i][0], Math.max(maxHeight, books[i][1]))); } dp[i][width] = res; return res; } }
-
复杂度
- 时间复杂度: O ( 2 n ) O(2^n) O(2n)
- 空间复杂度: O ( n ∗ s h e l f W i d t h ) O(n*shelfWidth) O(n∗shelfWidth)
-
dfs+记忆化:枚举选到哪个
-
实现:
定义 d f s ( i ) dfs(i) dfs(i)为摆放第 i i i本书及剩下的书全部摆放完毕需要的最小高度。那么 d f s ( 0 ) dfs(0) dfs(0)即为最终答案
class Solution { int[] dp; int[][] books; int shelfWidth; public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; dp = new int[n + 1]; this.books = books; this.shelfWidth = shelfWidth; return dfs(0); } public int dfs(int i){ if (i == books.length) return 0; if (dp[i] != 0) return dp[i]; int width = 0, maxHeight = 0, res = Integer.MAX_VALUE; for (int j = i; j < books.length; j++){ width += books[j][0]; if (width > shelfWidth) break;// 无法放书 maxHeight = Math.max(maxHeight, books[j][1]); res = Math.min(res, dfs(j + 1) + maxHeight); } dp[i]= res; return res; } }
-
复杂度
- 时间复杂度: O ( 2 n ) O(2^n) O(2n)
- 空间复杂度: O ( n ) O(n) O(n)
-
递推
-
实现
class Solution { public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; int[] dp = new int[n + 1]; for (int i = 0; i < n; i++){ int w = books[i][0], h = books[i][1]; dp[i + 1] = dp[i] + h;// 独立一层 for (int j = i - 1; j >= 0; j--){// 枚举可以选哪个 w += books[j][0]; if (w > shelfWidth) break; h = Math.max(h, books[j][1]); dp[i + 1] = Math.min(dp[i + 1], dp[j] + h); } } return dp[n]; } }
-
复杂度
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
-
工作计划的最低难度【LC1335】
你需要制定一份
d
天的工作计划表。工作之间存在依赖,要想执行第i
项工作,你必须完成全部j
项工作(0 <= j < i
)。你每天 至少 需要完成一项任务。工作计划的总难度是这
d
天每一天的难度之和,而一天的工作难度是当天应该完成工作的最大难度。给你一个整数数组
jobDifficulty
和一个整数d
,分别代表工作难度和需要计划的天数。第i
项工作的难度是jobDifficulty[i]
。返回整个工作计划的 最小难度 。如果无法制定工作计划,则返回 -1 。
dfs+记忆化
-
思路
题意可以转化为分割成d个子数组,使d个子数组的最大值之和最小。
-
寻找子问题:如果将后 [ k , n − 1 ] [k,n-1] [k,n−1]个任务在一天内完成,那么前面 [ 0 , k − 1 ] [0,k-1] [0,k−1]个任务需要在 d − 1 d-1 d−1天完成,因此找到了子问题,可以通过递归/动态规划来解决。(dfs+记忆化的形式最好理解)
-
定义dfs函数:定义 d f s ( i , j ) dfs(i,j) dfs(i,j)为在 i i i天完成 [ 0 , j ] [0,j] [0,j]个任务所需要的最小难度
-
递归入口:那么 d f s ( n − 1 , d ) dfs(n-1,d) dfs(n−1,d)即为答案
-
递归逻辑:
由于每一天都需要有工作任务,那么在决定第 i i i天的工作任务时,必须预留 i − 1 i-1 i−1个工作。因此在安排第 i i i天的工作任务时,我们枚举 [ i − 1 , j ] [i-1,j] [i−1,j]个任务,分割子数组,记录子数组中的最大值(当天的工作难度),然后递归到下一天,取最小值返回。
d f s ( i , j ) = m i n k = i − 1 j { d f s ( i − 1 , k − 1 ) + m a x p = k j ( j o b D i f f i c u l t y [ p ] ) } dfs(i,j)= min_{k= i-1}^{j}\{dfs(i-1,k-1)+max_{p=k}^{j}(jobDifficulty[p])\} dfs(i,j)=mink=i−1j{dfs(i−1,k−1)+maxp=kj(jobDifficulty[p])} -
递归边界:
只有一天时,必须完成所有任务
-
-
实现
(i可以整体缩小1)
class Solution { int[] jobDifficulty; int[][] memo; int res = Integer.MAX_VALUE; public int minDifficulty(int[] jobDifficulty, int d) { this.jobDifficulty = jobDifficulty; // 分割成d个子数组,使d个子数组的最大值之和最小 // dfs(i,j) j天完成[0,i]项工作所需要的最小难度 int n = jobDifficulty.length; if (n < d){ return -1; } memo = new int[d + 1][n]; for (int i = 0; i <= d; i++){ Arrays.fill(memo[i], -1); } return dfs(d, n - 1); } public int dfs(int i, int j){ // if (i < 0 || j <= 0) return 0; if (memo[i][j] != -1) return memo[i][j]; // 只有一天 if (i == 1){ int mx = 0; for (int k = 0; k <= j; k++){ mx = Math.max(mx, jobDifficulty[k]); } memo[i][j] = mx; return mx; } int res = Integer.MAX_VALUE; int mx = -1; // 枚举子数组范围 [i - 1, j] 留下i - 1个元素 for (int k = j; k >= i - 1; k--){ mx = Math.max(mx, jobDifficulty[k]); res = Math.min(res, mx + dfs(i - 1,k - 1)); } memo[i][j] = res; return res; } }
-
复杂度
- 时间复杂度: O ( n 2 d ) O(n^2d) O(n2d)
- 空间复杂度: O ( n d ) O(nd) O(nd)
-
递推
-
实现
class Solution { public int minDifficulty(int[] a, int d) { int n = a.length; if (n < d) return -1; var f = new int[d][n]; f[0][0] = a[0]; for (int i = 1; i < n; i++) f[0][i] = Math.max(f[0][i - 1], a[i]); for (int i = 1; i < d; i++) { for (int j = n - 1; j >= i; j--) { f[i][j] = Integer.MAX_VALUE; int mx = 0; for (int k = j; k >= i; k--) { mx = Math.max(mx, a[k]); // 从 a[k] 到 a[j] 的最大值 f[i][j] = Math.min(f[i][j], f[i - 1][k - 1] + mx); } } } return f[d - 1][n - 1]; } } 作者:灵茶山艾府 链接:https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/solutions/2271631/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-68nx/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
-
复杂度
- 时间复杂度: O ( n 2 d ) O(n^2d) O(n2d)
- 空间复杂度: O ( n d ) O(nd) O(nd)
-