1130.叶值的最小代价生成树.md

1130.叶值的最小代价生成树

/*
 * @lc app=leetcode.cn id=1130 lang=typescript
 *
 * [1130] 叶值的最小代价生成树
 */

// @lc code=start
function mctFromLeafValues(arr: number[]): number {}
// @lc code=end

解法 1: dfs

function mctFromLeafValues(arr: number[]): number {
  const n = arr.length,
    cache: [number, number][][] = Array.from({ length: n }, () => [])
  const dfs = (l = 0, r = n - 1): [number, number] => {
    if (l === r) return [arr[l], 0]
    if (cache[l][r] === undefined) {
      let sum = Infinity,
        max = -Infinity
      for (let i = l + 1; i <= r; i++) {
        const [lm, ls] = dfs(l, i - 1),
          [rm, rs] = dfs(i, r)
        max = Math.max(max, lm, rm)
        sum = Math.min(sum, ls + rs + lm * rm)
      }
      cache[l][r] = [max, sum]
    }
    return cache[l][r]
  }
  return dfs()[1]
}

Case

test.each([
  { input: { arr: [6, 2, 4] }, output: 32 },
  { input: { arr: [4, 11] }, output: 44 },
])('input: arr = $input.arr', ({ input: { arr }, output }) => {
  expect(mctFromLeafValues(arr)).toEqual(output)
})