410.分割数组的最大值

链接：410.分割数组的最大值
难度：Hard
标签：贪心、数组、二分查找、动态规划、前缀和
简介：给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。设计一个算法使得这 k 个子数组各自和的最大值最小。

题解 1 - typescript

• 编辑时间：2020-07-25
• 执行用时：188ms
• 内存消耗：39.68MB
• 编程语言：typescript
• 解法介绍：dp[i][j] = 分成i份时，只有前j个元素时的最小值。

function splitArray(nums: number[], m: number): number {
    const n = nums.length;
    const dp = new Array(n + 1)
        .fill(0)
        .map((_) => new Array(m + 1).fill(Infinity));
    dp[0][0] = 0;
    const sub = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) sub[i + 1] = sub[i] + nums[i];
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= Math.min(i, m); j++) {
        for (let k = 0; k < i; k++) {
            dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k]));
        }
        }
    }
    return dp[n][m];
}

题解 2 - python

• 编辑时间：2024-01-21
• 执行用时：7699ms
• 内存消耗：16.83MB
• 编程语言：python
• 解法介绍：dp[i][j] = 分成i份时，只有前j个元素时的最小值。

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[inf] * (n + 1) for _ in range(k + 1)]
        dp[1][0] = 0
        for i in range(1, n + 1): dp[1][i] = dp[1][i - 1] + nums[i - 1]
        for k in range(2, k + 1):
            for i in range(k, n + 1):
                num = 0
                for j in range(i, k - 1, -1):
                    num += nums[j - 1]
                    dp[k][i] = min(dp[k][i], max(dp[k - 1][j - 1], num))
        return dp[k][n]