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

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:

remove first and last element => cost will be gcd(first, last)

remove first and middle element => cost will be gcd(first, middle)

remove middle and last element => cost will be gcd(middle, last)

注：

在一个偶数大小的数组中，中间有两个元素。所以，把第二个中间元素当作中间元素。
gcd(x,y)代表x和y之间的Greatest Common Divisor

示例：

输入：[2、4、8、6]

输出：4

解释：

在第一个操作中删除第一个和中间的元素，cost = gcd(2,8) = 2
第二个操作去掉4和6，cost = gcd(4,6) = 2
总费用=2+2=4

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));

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

Minimum cost to empty an array by repeatedly removing first and middle, first and last, or middle and last elements

language-agnostic

arrays

algorithm

math

问题