欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 410. Split Array Largest Sum

程序员文章站 2022-06-17 18:24:37
...

Leetcode 410. Split Array Largest Sum

 

Leetcode 410. Split Array Largest Sum

 

 

 dp[i][j] 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值

i的范围是[1, j]

 

计算dp[i][j]时,对于所有1<=k<=j-1:

最后一个分组为nums[k+1]…nums[j]时,此时各个子数组中最大值为max(sum(nums[k+1:j+1]), dp[i-1][k])

遍历k得到最小的dp[i][j]

 

最终返回 dp[m][n] 即可

class Solution {
public:
	int splitArray(vector<int>& nums, int m) {
		int n = nums.size();
		vector<vector<int>> dp(m + 1, vector<int>(n, INT_MAX));
		dp[1][0] = nums[0];
		for (int j = 1; j < n; ++j) {
			dp[1][j] = dp[1][j - 1] + nums[j];
			for (int i = 2; i <= m; ++i) {
				// 分割成i-1份,最后一份为nums[k+1],...nums[j]
				for (int k = 0; k < j; ++k) {
					// sum_k = nums[k+1] + nums[k+2] + ... + nums[j]
					int sum_k = dp[1][j] - dp[1][k];
					dp[i][j] = min(dp[i][j], max(sum_k, dp[i - 1][k]));
				}
			}
		}

		return dp[m][n];
	}
};

 

相关标签: 算法