Представление натурального числа в виде суммы квадратов с использованием динамического программирования

Question

Задача состоит в том, чтобы найти минимальное количество квадратов, необходимое для суммирования с числом n.

Некоторые примеры:

min[ 1] = 1 (1²)
min[ 2] = 2 (1² + 1²)
min[ 4] = 1 (2²)
min[13] = 2 (3² + 2²)

Мне известно о четырех-теорема о квадрате , которая гласит, что любое натуральное число может быть представлено как сумма четырех квадратов.

Я пытаюсь решить это с помощью DP.

Это то, что я придумал(это не правильно)

min[i] = 1 where i is a square number
min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i

Как правильно DP решить эту проблему?

Answer 1

Я не уверен, является ли DP наиболее эффективным способом решения этой проблемы, но вы запросили DP.

min [i] = min (min [i - 1] + 1, 1 + min [i - prev]), где prev - квадратное число
Это близко, я бы написал условие как

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'

Обратите внимание, что для каждого i необходимо проверить различные возможные значения prev.

Вот простая реализация на Java.

Arrays.fill(min, Integer.MAX_VALUE);
min[0] = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j*j <= i; ++j) {
        min[i] = Math.min(min[i], min[i - j*j] + 1);
    }
}

Answer 2

Мне кажется, что ты рядом ...

Вы берете min () из двух слагаемых, каждый из которых равен min[i - p] + 1, где p равно 1 или некоторому другому квадрату Чтобы это исправить, просто возьмите min () из min[i - p] + 1 над all p (где p - квадрат Это будет правильный путь. Там может быть более быстрый путь.

Кроме того, это может улучшить читабельность, если вы дадите min[] и min() разные имена. : -)

P.S. Вышеупомянутый подход требует, чтобы вы запомнили min[], либо явно, либо как часть вашей структуры DP. В противном случае сложность алгоритма из-за рекурсии будет примерно такой: O (sqrt (n)!) :-P, хотя средний случай может быть намного лучше.

P.P.S. Смотрите ответ @ Никиты для хорошей реализации. К которому я бы добавил следующие оптимизации ... (Я не придираюсь к его реализации - он представил ее как простую.)

1. Проверьте, является ли n идеальным квадратом, перед входом во внешний цикл: если это так, min [n] = 1, и все готово.
2. Проверьте, является ли я идеальным квадратом перед входом во внутренний цикл: если это так, min [i] = 1, и пропустите внутренний цикл.
3. Выпадение из внутреннего цикла, если min [i] было установлено в 2, потому что это не улучшится (если бы это можно было сделать с одним квадратом, мы бы никогда не вошли во внутренний цикл, благодаря предыдущему оптимизация).
4. Интересно, можно ли изменить условие завершения во внутреннем цикле, чтобы уменьшить количество итераций, например, j*j*2 <= i или даже j*j*4 <= i. Я так думаю, но у меня не до конца разбирается.

5. Для больших i было бы быстрее вычислить предел для j перед внутренним циклом и сравнивать j непосредственно с ним для условия завершения цикла, а не возводить в квадрат j на каждой итерации внутреннего цикла. Э.Г.

   float sqrti = Math.sqrt(i);
   for (int j = 1; j <= sqrti; ++j) {
   

   С другой стороны, вам все равно понадобится j ^ 2 для шага рекурсии, поэтому, пока вы его храните, вы можете использовать его.

Answer 3

Я представляю обобщенный очень эффективный алгоритм динамического программирования, чтобы найти минимальное число натуральных чисел с заданной степенью для достижения заданной цели в JavaScript.

Например, для достижения 50000 с целыми числами 4-й степени результат будет [10,10,10,10,10] или для достижения 18571 с целыми числами 7-й степени - [3,4]. Этот алгоритм будет работать даже с рациональными степенями, такими как достижение 222 с целыми числами ³ / ₅ ^th мощность будет [ 32, 32, 243, 243, 243, 3125 ]

function getMinimumCubes(tgt,p){
  var maxi = Math.floor(Math.fround(Math.pow(tgt,1/p))),
      hash = {0:[]},
       pow = 0,
         t = 0;
  for (var i = 1; i <= maxi; i++){
    pow = Math.fround(Math.pow(i,p));
    for (var j = 0; j <= tgt - pow; j++){
      t = j + pow;
      hash[t] = hash[t] ? hash[t].length <= hash[j].length ? hash[t]
                                                           : hash[j].concat(i)
                        : hash[j].concat(i);
    }
  }
  return hash[tgt];
}

var target = 729,
    result = [];
console.time("Done in");
result = getMinimumCubes(target,2);
console.timeEnd("Done in");
console.log("Minimum number of integers to square and add to reach", target, "is", result.length, "as", JSON.stringify(result));

console.time("Done in");
result = getMinimumCubes(target,6);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 6th power and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 500;
console.time("Done in");
result = getMinimumCubes(target,3);
console.timeEnd("Done in");
console.log("Minimum number of integers to cube and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 2017;
console.time("Done in");
result = getMinimumCubes(target,4);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 4th power and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 99;
console.time("Done in");
result = getMinimumCubes(target,2/3);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 2/3th power and add to reach", target, "are", result);

Answer 4

Для разнообразия вот еще один ответ:

Определите minsq [i, j] как минимальное количество квадратов из {1 ^ 2, 2 ^ 2, ..., j ^ 2}, суммирующих до i. Тогда рекурсия:

minsq[i, j] = min(minsq[i - j*j, j] + 1, minsq[i, j - 1])

То есть, для вычисления minsq [i, j] мы либо используем j ^ 2, либо нет. Наш ответ для n таков:

minsq[n, floor(sqrt(n))]

Этот ответ, возможно, концептуально проще, чем представленный ранее, но с точки зрения кода это сложнее, так как нужно быть осторожным с базовыми вариантами. Временная сложность для обоих ответов асимптотически одинакова.