Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.
Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

class Solution {
    function numSquares($n) {
        $dp = array_fill(0, $n + 1, PHP_INT_MAX);
        $dp[0] = 0;
        
        $maxSquareIndex = floor(sqrt($n)) + 1;
        $squareNums = array_fill(0, $maxSquareIndex, 0);
        for ($i = 1; $i < $maxSquareIndex; ++$i) {
            $squareNums[$i] = $i * $i;
        }
        
        for ($i = 1; $i <= $n; ++$i) {
            for ($s = 1; $s < $maxSquareIndex; ++$s) {
                if ($i < $squareNums[$s]) break;
                $dp[$i] = min($dp[$i], $dp[$i - $squareNums[$s]] + 1);
            }
        }
        
        return $dp[$n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний