1799.n-次操作后的最大分数和.md

1799.n-次操作后的最大分数和

/*
 * @lc app=leetcode.cn id=1799 lang=typescript
 *
 * [1799] N 次操作后的最大分数和
 */

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

解法 1: 记忆化搜索

function maxScore(nums: number[]): number {
  const n = nums.length
  const g: number[][] = Array.from({ length: n }, () => [])
  const gcd = (a: number, b: number) => (b ? gcd(b, a % b) : a)
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      g[i][j] = g[j][i] = gcd(nums[i], nums[j])
    }
  }
  const cache = []
  const dfs = (state: number) => {
    if (cache[state] !== undefined) return cache[state]
    let cnt = 0
    for (let i = 0; i < n; i++) if (!(state & (1 << i))) cnt++
    let res = 0
    for (let i = 0; i < n; i++) {
      if (state & (1 << i)) continue
      for (let j = i + 1; j < n; j++) {
        if (state & (1 << j)) continue
        res = Math.max(res, dfs(state | (1 << i) | (1 << j)) + (cnt * g[i][j]) / 2)
      }
    }
    cache[state] = res
    return res
  }
  return dfs(0)
}

Case

test.each([
  {
    input: {
      nums: [
        39759, 619273, 859218, 228161, 944571, 597983, 483239, 179849, 868130, 909935, 912143, 817908, 738222, 653224,
      ],
    },
    output: 782,
  },
  { input: { nums: [1, 2] }, output: 1 },
  { input: { nums: [3, 4, 6, 8] }, output: 11 },
  { input: { nums: [1, 2, 3, 4, 5, 6] }, output: 14 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(maxScore(nums)).toEqual(output)
})