高淳网站建设/数据分析师证书
leetcode410. 分割数组的最大值
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
- 1 ≤ n ≤ 1000
- 1 ≤ m ≤ min(50, n)
示例:
输入:
nums = [7,2,5,10,8]
m = 2输出:
18解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。方法：动态规划
思路：
这道题应该使用动态规划的方法。
我们设dp(i,j)表示将前i+1个数分为j+1组情况下的答案，那么最后的答案即为dp(n-1,m-1)。
下面我们考虑状态转移方程，对于dp(i,j)，我们可知，它与dp(x,j-1)有关。即最后一个分组在哪，此时如果x=1，那么此时最后一个分组为nums[1:j+1]，此时这种分组情况的和的最大值为max(dp(x,j-1)，sum(nums[1:j+1]))。那么我们遍历所有可能的x，找到这些情况中的最小值，即为dp(i,j)的值。x可能的取值为[j-1，i-1]。
所以，状态转移方程为：
下面考虑边界条件，dp(0,0) = nums[0]。
我们可知，任意时刻，i>=j才行。所以我们先遍历，填写所有的dp(i,i)。
然后考虑j = 0的情况，即整个分为1组，那么此时的dp即为前i的和，所以遍历填写dp(i,0)。
在正式遍历填写dp的时候，按照以下的循环：
# i从1开始for i in range(1,n):# j需要小于等于i，且j<m，且j==i的上面已经填写，for j in range(1,min(i,m)):# k的范围for k in range(j-1,i):同时，我们还发现，dp[:] [0]对应的数组即为前缀和数组，因此sum(nums[k+1:i+1])可以通过dp[i][0]-dp[k][0]求得。因此状态转移方程可以改为：
最后答案返回dp(n-1,m-1)即可。
代码：
代码：
Python3：
class Solution:def splitArray(self, nums: List[int], m: int) -> int:n = len(nums)# dp[i][j]表示前i+1个数，分成j+1组，各自和最大值的最小# 答案为dp[n-1][m-1]dp = [[float('inf') for _ in range(m)] for _ in range(n)]dp[0][0] = nums[0]# 将一个数分为一组的情况，最多是前m个数分为m组for i in range(1,m):dp[i][i] = max(dp[i-1][i-1],nums[i])# 将i+1个数分为1组，那么答案即为数组的和，同样也表示前缀和for i in range(1,n):dp[i][0] = dp[i-1][0] + nums[i]# 开始填写dp数组。# dp[i][j] = min(max(dp[k][j-1],sum(nums[k+1:i+1]))) k取值为(j-1,i)# sum(nums[k+1:i+1])可以通过dp[i][0]-dp[k][0]求得。for i in range(1,n):for j in range(1,min(i,m)):for k in range(j-1,i):dp[i][j] = min(dp[i][j],max(dp[k][j-1],dp[i][0]-dp[k][0]))return (int)dp[n-1][m-1]Cpp：
class Solution {
public:int splitArray(vector<int>& nums, int m) {int n = nums.size();vector<vector<long long>> dp(n, vector<long long>(m, LLONG_MAX));dp[0][0] = nums[0];for (int i = 1;i < n;++i) dp[i][0] = dp[i-1][0] + nums[i];for (int i = 1;i < m;++i) dp[i][i] = max(dp[i-1][i-1],(long long)nums[i]);for (int i = 1;i < n;++i){for (int j = 1;j < min(i,m);++j){for (int k = j-1; k<i ;++k){dp[i][j] = min(dp[i][j],max(dp[k][j-1],dp[i][0]-dp[k][0]));}}}return (int)dp[n-1][m-1];}
};
结果：
