algorithm - 算法-要获得“令人印象深刻”的数字集，您必须进行多少次更改

问题
一组令人印象深刻的数字是一组，其中每个数字包含k个数量的k个数字。
例如(5, 5, 5, 5, 5)，(2, 2, 3, 3, 3, 1)和(2, 2, 1)是令人印象深刻的一组。
(3, 3, 2)不是一个令人印象深刻的集合，因为有两个3s（应该是三个）和一个2（应该是两个）。
有一个n整数ai的列表，因此（1≤n≤2000，1≤ai≤2000）。
找到最小的变化量，得到一个令人印象深刻的设置。你可以一次换一个号码。顺序无关紧要。最后一盘是什么并不重要。
实例
输入：（3，4，3，2，1）—>（3，3，3，2，1）—>（3，3，3，2，2）=>输出：2
输入：（5，5，5，5，5，5，5）—>（5，5，5，5，5，5，5，2）—>（5，5，5，5，5，2，2）=>输出：2
输入：（2，2，3，3）->（2，3，3）->（1，3，3）==>输出：2
输入/输出
函数的输入是一个列表输出是表示最小变化量的int。
旁注
程序应该是用C++编写的，内存容量为64 MB。当然，我并不是在寻求一个解决方案，而是一个关于如何在算法方面做的提示。

最佳答案

这里有一个递归公式，其中g(i, j)表示实现基数i的集合所需的最少更改，考虑到j以内的数字。O(n*n)搜索空间：

function f(A){
  const n = A.length;
  const counts = new Array(n + 1).fill(0);

  for (let i of A)
    if (i <= n)
      counts[i]++;

  const h = {};

  function g(i, j){
    const key = `${i},${j}`;

    if (h.hasOwnProperty(key))
      return h[key];
    if (i == 0 || (i==j && j==counts[j]))
      return h[key] = 0;
    if (i < 0 || j < 1)
      return h[key] = Infinity;

    return h[key] = Math.min(
      // use j
      Math.max(j - counts[j], 0) + g(i - j, j - 1),
      // don't use j
      g(i, j - 1)
    )
  }
  return g(n, n);
}

for (i of [
  [2,2,3,3], // 2
  [3,4,3,2,1], // 2
  [5,5,5,5,5,5,5], // 2
  [1,2,3,4,5], // 3
  [1,1,2,3,4,5], // 3
  [5], // 1
  [3,2,1,1,1] // 3
]) console.log(JSON.stringify(i), f(i));

let largeRandomInput = [];
for (let i=0; i<2000; i++)
  largeRandomInput.push(~~(Math.random() * 2001));

const t0 = performance.now();
console.log(f(largeRandomInput));
const t1 = performance.now();
console.log((t1 - t0) + " milliseconds.")

关于algorithm - 算法-要获得“令人印象深刻”的数字集，您必须进行多少次更改，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53598090/