1000.合并石头的最低成本.md

1000.合并石头的最低成本

/*
 * @lc app=leetcode.cn id=1000 lang=typescript
 *
 * [1000] 合并石头的最低成本
 */

// @lc code=start
function mergeStones1(a: number[], m: number): number {}

// @lc code=end

解法 1: 记忆化搜索

function mergeStones(stones: number[], k: number): number {
  const n = stones.length
  if ((n - 1) % (k - 1) !== 0) return -1
  const sums: number[] = []
  for (let i = 0; i < n; i++) sums[i] = (sums[i - 1] ?? 0) + stones[i]
  const cache: number[][][] = Array.from({ length: n }, () => Array.from({ length: n }, () => []))
  const dfs = (l: number, r: number, len: number): number => {
    if (l === r) {
      if (len === 1) return 0
      return Infinity
    }

    if (len === 1) {
      if (l === r) return stones[l]
      if ((r - l) % (k - 1) !== 0) return Infinity
      if (r - l === k - 1) return sums[r] - (sums[l - 1] ?? 0)
    }
    if (l === r) return Infinity
    if (cache[l][r][len] !== undefined) return cache[l][r][len]
    const t = len === 1 ? k : len
    let res = dfs(l + 1, r, t - 1)
    for (let i = l; i + k - 1 < r; i++) {
      let ans = dfs(l, i + k - 1, 1)
      ans += dfs(i + k, r, t - 1)
      res = Math.min(res, ans)
    }
    if (len === 1) res += sums[r] - (sums[l - 1] ?? 0)
    cache[l][r][len] = res
    return res
  }
  return dfs(0, n - 1, 1)
}

Case

test.each([
  {
    input: { stones: [16, 43, 87, 30, 4, 98, 12, 30, 47, 45, 32, 4, 64, 14, 24, 84, 86, 51, 11, 22, 4], k: 2 },
    output: 3334,
  },
  { input: { stones: [7, 7, 8, 6, 5, 6, 6], k: 3 }, output: 83 },
  { input: { stones: [3, 5, 1, 2, 6], k: 3 }, output: 25 },
  { input: { stones: [3, 2, 4, 1], k: 2 }, output: 20 },
  { input: { stones: [3, 2, 4, 1], k: 3 }, output: -1 },
  { input: { stones: [3, 5, 1, 2, 6], k: 3 }, output: 25 },
])('input: stones = $input.stones, k = $input.k', ({ input: { stones, k }, output }) => {
  expect(mergeStones(stones, k)).toEqual(output)
})