1039.多边形三角剖分的最低得分.md

1039.多边形三角剖分的最低得分

/*
 * @lc app=leetcode.cn id=1039 lang=typescript
 *
 * [1039] 多边形三角剖分的最低得分
 */

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

解法 1: 记忆化搜索

function minScoreTriangulation(values: number[]): number {
  const n = values.length
  const cache: number[][] = Array.from({ length: n }, () => [])

  const dfs = (i: number, j: number) => {
    if (i + 2 === j) return values[i] * values[i + 1] * values[j]
    if (cache[i][j] !== undefined) return cache[i][j]
    let res = Infinity
    for (let k = i + 1; k < j; k++) {
      let ans = values[i] * values[j] * values[k]
      if (k > i + 1) ans += dfs(i, k)
      if (k < j - 1) ans += dfs(k, j)
      res = Math.min(res, ans)
    }
    cache[i][j] = res
    return res
  }
  return dfs(0, n - 1)
}

Case

test.each([
  {
    input: {
      values: [
        17, 40, 14, 95, 44, 88, 47, 86, 91, 74, 73, 52, 29, 56, 89, 61, 94, 79, 87, 40, 89, 58, 48, 13, 62, 73, 45, 15,
        6, 12, 79, 72, 18, 55, 35, 27, 96, 32, 49, 17, 7, 60, 83, 65, 93, 99, 49, 84, 78, 5,
      ],
    },
    output: 813710,
  },
  { input: { values: [69, 22, 21, 27, 26, 62, 69, 81, 55, 85, 95, 40, 91, 33, 72, 88, 86] }, output: 1334781 },
  { input: { values: [1, 2, 3] }, output: 6 },
  { input: { values: [3, 7, 4, 5] }, output: 144 },
  { input: { values: [1, 3, 1, 4, 1, 5] }, output: 13 },
])('input: values = $input.values', ({ input: { values }, output }) => {
  expect(minScoreTriangulation(values)).toEqual(output)
})