410. 分割数组的最大值

Updated on with 0 views and 0 comments

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10<sup>6</sup>
  • 1 <= m <= min(50, nums.length)

分析

这是动态规划中很经典的划分问题,和1335题的任务调度问题很相似,都是给一个集合,让你划分成XXX,然后给你一个规则来找出这个规则下的最优解。

  • 解决动态规划,最重要的就是明确子问题,找到状态转移方程,明确初始条件,基本就完成了。
  • 仔细分析这道题,给定一个数组nums[i] (0 <= i <= n),让你划分为m分,然后求m分中和值最大的划分方式中的最小值。
  • 很明显子问题是对于一个数组nums[i] (0 <= i <= n-1),前i位数组划分为m-1分,然后求m-1分中和值最大的划分方式中的最小值。
  • 那就可以使用一个备忘录,dp[n][m] 来表示 把n个数 m分中和值最大的划分方式中的最小值。对可以用变量k对n个数进行枚举 ,其中前 k个数被分割为 m-1 段,而第 k+1到 n 个数为第 m 段。第 m 段的和值可以用前缀和的方式以O(1)的时间复杂度获得。
  • 求m-1段的最大值就是: max(dp[k][m-1], sub(k + 1, n)
    状态转移方程就是dp[n][m] = min(dp[n][m], maxValue), maxValue = max(dp[k][m-1], sub(k + 1, n) (0 <= k < n)。

代码:

func splitArray(nums []int, m int) int {
    n := len(nums)
    dp := make([][]int, n + 1)
    sub := make([]int, n + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, m + 1)
        for j := 0; j < len(dp[i]); j++ {
            dp[i][j] = 1 << 31 - 1
        }
    }

    // 前缀和加速
    for i := 0; i < n; i++ {
        sub[i + 1] = sub[i] + nums[i]
    }
    
    dp[0][0] = 0
    for i := 1; i <= n; i++ {
        // 从分成1份开始,一直到分成m份
        for j := 1; j <= m; j++ {
            // 然后看前k个数,分成j-1份,
            // 就是前半部分的解(备忘录已经算好),和最后一部分的和值(前缀和)比较,来做状态转移
            for k := 0; k < i; k++ {
                // sub[i] - sub[k] 使用前缀和,快速求出最后一段的和值
                dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]))
            }
        }
    }
    return dp[n][m]
}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

标题:410. 分割数组的最大值
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2021/09/14/1631602150482.html