Разбор задачи «Каменные плиты»

Идея задачи

Дано число n. Нужно представить его в виде суммы полных квадратов:

• 1 = 1^2
• 4 = 2^2
• 9 = 3^2
• 16 = 4^2
• и так далее

Каждый квадрат можно использовать сколько угодно раз. Требуется найти минимальное количество таких квадратов, сумма которых равна n.

Например:

• 12 = 4 + 4 + 4, ответ 3
• 13 = 4 + 9, ответ 2

Это классическая задача на динамическое программирование.

Наблюдение

Пусть мы хотим найти ответ для числа x.

Тогда последний использованный квадрат мог быть любым из таких:

• 1
• 4
• 9
• 16
• ...
• любой i^2, для которого i^2 <= x

Если последним квадратом был i^2, то до этого мы уже должны были набрать сумму x - i^2.

Значит, если мы знаем оптимальный ответ для x - i^2, то можем получить кандидат на ответ для x:

dp[x - i^2] + 1

Нужно взять минимум по всем допустимым квадратам.

Динамическое программирование

Обозначим:

• dp[x] — минимальное количество квадратов, которыми можно набрать сумму x

База:

• dp[0] = 0, потому что для суммы 0 не нужно ни одного числа

Переход:

• dp[x] = min(dp[x], dp[x - i * i] + 1) для всех i, где i * i <= x

Мы считаем значения dp слева направо: от 1 до n.

Почему это работает

Рассмотрим любое число x.

В оптимальном разложении числа x на квадраты обязательно есть последний квадрат. Пусть это квадрат i^2. Тогда оставшаяся сумма равна x - i^2.

Если бы для x - i^2 мы брали не оптимальное количество квадратов, а какое-то большее, то и для x решение тоже не было бы оптимальным. Значит, оптимальный ответ для x действительно строится из оптимального ответа для x - i^2 и ещё одного квадрата.

Следовательно, достаточно перебрать все возможные последние квадраты и выбрать лучший вариант.

Пример работы

Рассмотрим n = 12.

Будем постепенно считать:

• dp[0] = 0
• dp[1] = 1 (1)
• dp[2] = 2 (1 + 1)
• dp[3] = 3 (1 + 1 + 1)
• dp[4] = 1 (4)
• dp[5] = 2 (4 + 1)
• dp[6] = 3 (4 + 1 + 1)
• dp[7] = 4
• dp[8] = 2 (4 + 4)
• dp[9] = 1 (9)
• dp[10] = 2 (9 + 1)
• dp[11] = 3 (9 + 1 + 1)
• dp[12] = 3 (4 + 4 + 4)

Ответ: 3.

Оценка сложности

Для каждого x от 1 до n мы перебираем все квадраты, не превосходящие x.

Таких квадратов порядка sqrt(x), значит общая сложность:

• Время: O(n * sqrt(n))
• Память: O(n)

При n <= 10^4 это работает быстро.

Типичные ошибки

1. Неправильная база

Если забыть задать dp[0] = 0, переходы не будут работать корректно.

2. Слишком маленькое начальное значение

Обычно массив dp сначала заполняют очень большим числом, чтобы потом искать минимум.

3. Ошибка в переборе квадратов

Нужно проверять условие i * i <= x, а не i <= x.

4. Попытка жадного решения

Нельзя всегда брать самый большой возможный квадрат. Например, для некоторых чисел такой подход не даёт оптимума.

Эталонное решение на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> dp(n + 1, 1000000000);
    dp[0] = 0;

    for (int x = 1; x <= n; x++) {
        for (int i = 1; i * i <= x; i++) {
            dp[x] = min(dp[x], dp[x - i * i] + 1);
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

Эталонное решение на Python

n = int(input())

dp = [10**9] * (n + 1)
dp[0] = 0

for x in range(1, n + 1):
    i = 1
    while i * i <= x:
        dp[x] = min(dp[x], dp[x - i * i] + 1)
        i += 1

print(dp[n])

Пошаговая структура решения

Можно мыслить так:

1. Для каждого числа от 0 до n хотим знать оптимальный ответ.
2. Ответ для 0 известен сразу.
3. Для каждого x пробуем выбрать последний квадрат.
4. Смотрим, какой ответ был у остатка x - i^2.
5. Добавляем один квадрат и обновляем минимум.

Это и есть стандартная схема динамики по префиксу значений.

Почему это хорошая учебная задача

Эта задача полезна тем, что тренирует сразу несколько важных идей:

• построение динамики по значениям
• переход через «последний шаг»
• перебор допустимых состояний
• аккуратную работу с минимумом

После неё удобно изучать и более общие задачи, где нужно минимизировать число предметов, шагов или операций.

Вывод

Задача решается через динамическое программирование.

Мы храним dp[x] — минимальное количество квадратов для суммы x, и для каждого x перебираем все возможные квадраты i^2.

Итоговый ответ находится в dp[n].

Такое решение простое, надёжное и хорошо подходит как эталонное.