arrays - 通过重复删除第一个和中间、第一个和最后一个或中间和最后一个元素来清空数组的最小成本

Question

这个问题是在一次采访中问到我的，我无法想出一个最佳的解决方案。
题

Given an even size array, we can perform any operation on the array, until the array becomes empty such that the overall cost should be minimum.

Operations:

1. remove first and last element => cost will be gcd(first, last)
2. remove first and middle element => cost will be gcd(first, middle)
3. remove middle and last element => cost will be gcd(middle, last)

注:

在偶数数组中，有两个中间元素。因此，将第二个中间元素视为中间元素。

gcd(x,y) 代表 Greatest Common Divisor x 和 y 之间

示例:
输入:[2, 4, 8, 6]
输出:4
解释:

在第一个操作中删除第一个和中间元素，cost = gcd(2,8) = 2

在第二个操作中删除 4 和 6，cost = gcd(4,6) = 2

总成本 = 2+2 = 4

我的方法是比较所有 3 个操作成本，以最小的为准，直到数组为空。而且，那个 没用 .

Answer 1

无论我们执行操作的顺序如何，都可以用四个指针来描述列表的状态，这些指针准确地描述了列表中剩余的两个连续部分。
这些指针与一组特定的规则相关，这些规则限制了可能实现的状态。我将从使用四个指针组合开始，并使用内存状态进行递归。
我们可以通过观察两个连续部分的长度可以相差 0 或 2 来进一步减少状态。稍后我将尝试更新此答案。
JavaScript 代码(在 Python 中随机测试蛮力可用 here):

function gcd(x, y){
  while(y)
    [x, y] = [y, x % y];
  return x;
}

function f(A){
  const memo = {};
  const n = A.length;
  const mid = n / 2;
  
  function g(l0, l1, r0, r1){
    const key = String([l0, l1, r0, r1]);

    if (memo.hasOwnProperty(key))
      return memo[key];
    
    const len_l = l1 - l0 + 1;
    const len_r = r1 - r0 + 1;

    if (len_l + len_r == 2){
      if (len_r && len_l)
        return gcd(A[l0], A[r0]);
      else if (len_l)
        return gcd(A[l0], A[l0 + 1]);
      else
        return gcd(A[r0], A[r0 + 1]);
    }

    let a = A[l0];
    let b = A[r1];

    const outer = gcd(a, b) + g(l0 + 1, l1, r0, r1 - 1);

    if (len_r >= len_l)
      var mid = r0 + (len_l + len_r) / 2 - len_l;
    else
      var mid = l0 + (len_l + len_r) / 2;

    b = A[mid];
    
    const _l1 = l1 - (mid == l1 ? 1 : 0);
    const _r0 = r0 + (mid == r0 ? 1 : 0);

    const left = gcd(a, b) + g(l0 + 1, _l1, _r0, r1);

    a = A[r1];

    const right = gcd(b, a) + g(l0, _l1, _r0, r1 - 1);

    return memo[key] = Math.min(outer, left, right);
  }
  
  return g(0, mid - 1, mid, n - 1);
}

let A = [2, 4, 8, 6];
console.log(JSON.stringify(A));
console.log(f(A));

A = [8,5,21,10,25,9]
console.log(JSON.stringify(A));
console.log(f(A));

const n = 200;
A = [];

for (let i=0; i<n; i++)
  A.push(i + 1);

console.log(JSON.stringify(A));
console.log(f(A));