按照某种形式分割数组以获得最值
希望看了本文对你有所帮助，参考其他题解写成，取其精华，做以笔记，如有描述不清楚或者错误麻烦指正，不胜感激，不喜勿喷！
最大平均值的和分组【LC813】
You are given an integer array nums and an integer k. You can partition the array into at most k 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个连续子数组时，得到的最大分数
2.确定递推公式
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]; } }
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 位整数。
- 思路
实现
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]; } }
填充书架【LC1105】
给定一个数组
books，其中books[i] = [thicknessi, heighti]表示第i本书的厚度和高度。你也会得到一个整数shelfWidth。按顺序 将这些书摆放到总宽度为
shelfWidth的书架上。先选几本书放在书架上（它们的厚度之和小于等于书架的宽度
shelfWidth），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。
- 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
dfs+记忆化：选或不选
- 思路：
感觉递推的形式不是很好写，所以一开始的想法是dfs+记忆化。每遇到一本书，我们可以选择新建一层放置这本书，也可以选择在上一次继续放置这本书，影响结果的有两个因素：
该层已经摆放的书的宽度以及最大高度。因此在dfs过程需要记录这两个值，定义
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; } }
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; } }
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]; } }
工作计划的最低难度【LC1335】
你需要制定一份
d天的工作计划表。工作之间存在依赖，要想执行第i项工作，你必须完成全部j项工作（0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。
dfs+记忆化
- 思路
题意可以转化为分割成d个子数组，使d个子数组的最大值之和最小。
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; } }
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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
