410.分割数组的最大值.md

410.分割数组的最大值

/*
 * @lc app=leetcode.cn id=410 lang=typescript
 *
 * [410] 分割数组的最大值
 */

// @lc code=start
function splitArray(nums: number[], m: number): number {}
// @lc code=end

解法 1: 动态规划

关键: 连续子数组

1. 子问题: 将包括 i 之前的数字,分成 k 份后,子数组和的最大值最小
2. 状态:
   • i: 第 i 个数字
   • j: 将前 i 个数字分成 j 份
   • dp[i][j]: 前 i 个数字分成 j 份子数组的最小最大值
3. DP 方程:
   • k: 将 i 个数字分成 j 份,其中最后一个索引为 k
   • dp[i][j] = min(dp[i][j],max(dp[k][j-1],prefixsum(k+1 ~ i)))
4. 边界:
   • dp[i][0]=preSum[i]

function splitArray(nums: number[], m: number): number {
  const preSum = nums.reduce<number[]>((p, n, i) => [...p, p[i] + n], [0])
  const dp = new Array(nums.length + 1).fill(0).map((_, i) => [preSum[i], ...new Array(m - 1).fill(Infinity)])

  for (let i = 1; i <= nums.length; i++) {
    for (let j = 2; j <= Math.min(m, i); j++) {
      for (let k = j - 1; k < i; k++) {
        dp[i][j - 1] = Math.min(dp[i][j - 1], Math.max(dp[k][j - 2], preSum[i] - preSum[k]))
      }
    }
  }

  return dp[nums.length][m - 1]
}

Case

test.each([
  { input: { nums: [7, 2, 5, 10, 8], m: 2 }, output: 18 },
  { input: { nums: [1, 2, 3, 4, 5], m: 2 }, output: 9 },
  { input: { nums: [1, 4, 4], m: 3 }, output: 4 },
])(`input: nums = $input.nums, m = $input.m`, ({ input: { nums, m }, output }) => {
  expect(splitArray(nums, m)).toBe(output)
})