【LeetCode: 1043. 分隔数组以得到最大和 | 暴力递归=＞记忆化搜索=＞动态规划 | 线性dp 区间dp】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 1043. 分隔数组以得到最大和

⛲ 题目描述

给你一个整数数组 arr，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

示例 1：

输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]
示例 2：

输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83
示例 3：

输入：arr = [1], k = 1
输出：1

提示：

1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length

🌟 线性dp&求解思路&实现代码&运行结果

⚡ 暴力递归

🥦 求解思路

1. 首先根据题目的意思我们知道，题目让我们去求将数组划分成多个长度不超过k的子数组，每一个子数组的值更新为当前子数组中最大的值，最后求得所有划分方案中所有子数组最大的和并返回。
2. 那么这个题我们该怎么想呢？因为可以划分的长度最大是k，所以我们可以枚举所有k的选择；
3. 那么什么时候去求每个子数组贡献的结果呢？我们可以在遍历的时候，记录当前选择长度内的最大值，然后在调用递归的时候通过之前子数组中的最大值*个数累加到最终的结果中；
4. 有了基本的思路，接下来我们就来一起实现代码吧。

🥦 实现代码

class Solution {public int maxSumAfterPartitioning(int[] arr, int k) {return process(0,arr,k);}public int process(int index,int[] arr,int k){if(index>=arr.length) return 0;int max=0,num=0;for(int i=index;i<Math.min(index+k,arr.length);i++){num=Math.max(num,arr[i]);max=Math.max(max,process(i+1,arr,k)+num*(i-index+1));}return max;}
}

🥦 运行结果

时间超限了，不要紧哦，我还有锦囊妙计！

⚡ 记忆化搜索

🥦 求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

🥦 实现代码

class Solution {int[] dp;public int maxSumAfterPartitioning(int[] arr, int k) {dp=new int[arr.length];Arrays.fill(dp,-1);return process(0,arr,k);}public int process(int index,int[] arr,int k){if(index>=arr.length) return 0;if(dp[index]!=-1) return dp[index];int max=0,num=0;for(int i=index;i<Math.min(index+k,arr.length);i++){num=Math.max(num,arr[i]);max=Math.max(max,process(i+1,arr,k)+num*(i-index+1));}return dp[index]=max;}
}

🥦 运行结果

⚡ 动态规划

🥦 求解思路

1. 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。

🥦 实现代码

class Solution {int[] dp;public int maxSumAfterPartitioning(int[] arr, int k) {int n=arr.length;dp=new int[n+1];for(int index=n-1;index>=0;index--){int max=0,num=0;for(int i=index;i<Math.min(index+k,n);i++){num=Math.max(num,arr[i]);max=Math.max(max,dp[i+1]+num*(i-index+1));}dp[index]=max;}return dp[0];}
}

🥦 运行结果

🌟 区间dp&求解思路&实现代码&运行结果

⚡ 暴力递归

🥦 求解思路

1. 为什么会想到这种递归思路呢？因为题目要我们从开始位置到结束位置进行切割子数组，每个子数组的长度最多可能达到k，此时我们从0位置开始，可以选择的下一个位置小于k即可（[0_k-1]都是可以的），如果说此时我们选择了[0_k-2]进行切割，那么后续的问题就拆解成了[k-1_n-1]的规模，那么整个问题的求解是相同的，并且大规模可以拆解为小规模，此时我们通过递归来做就可以，后续直接改成动态规划。
2. 有了具体的实现思路，接下来我们就来一起看一下代码的实现。

🥦 实现代码

class Solution {public int maxSumAfterPartitioning(int[] arr, int k) {return process(0,arr,k,arr.length-1);}public int process(int left,int[] arr,int k,int right){if(left>right) return 0;if(right-left<k){int num=0;for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);return num*(right-left+1);}int max=0;for(int i=left;i<left+k;i++){max=Math.max(max,process(left,arr,k,i)+process(i+1,arr,k,right));}return max;}
}

🥦 运行结果

⚡ 记忆化搜索

🥦 求解思路

1. 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

🥦 实现代码

class Solution {int[][] dp;public int maxSumAfterPartitioning(int[] arr, int k) {int n=arr.length;dp=new int[n][n];for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);return process(0,arr,k,arr.length-1);}public int process(int left,int[] arr,int k,int right){if(left>right) return 0;if(right-left<k){int num=0;for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);return num*(right-left+1);}if(dp[left][right]!=-1) return dp[left][right];int max=0;for(int i=left;i<left+k;i++){max=Math.max(max,process(left,arr,k,i)+process(i+1,arr,k,right));}return dp[left][right]=max;}
}

🥦 运行结果

⚡ 动态规划

🥦 求解思路

1. 按照我们之前递归和记忆化搜索的思路，通过动态规划实现出来。

🥦 实现代码

class Solution {int[][] dp;public int maxSumAfterPartitioning(int[] arr, int k) {int n=arr.length;dp=new int[n][n];for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);for(int left=0;left<n;left++){for(int right=0;right<n;right++){if(right-left<k){int num=0;for(int i=left;i<=right;i++) num=Math.max(num,arr[i]);dp[left][right]=num*(right-left+1);}}}for(int left=n-k-1;left>=0;left--){for(int right=left+k-1;right<n;right++){int max=0;for(int i=left;i<left+k;i++){max=Math.max(max,dp[left][i]+dp[i+1][right]);}dp[left][right]=max;}}return dp[0][n-1];}
}

🥦 运行结果

💬 共勉