База, порядок и недостижимые состояния

Формулу перехода обычно выписывают правильно. Неверный ответ приходит с трёх других сторон.

База

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

Правило, которое почти всегда спасает: база — это нейтральный элемент операции перехода.

операция	нейтральный элемент	база
сумма (считаем количество)	0	пустой способ — это 1, остальное 0
минимум	$+\infty$	старт — 0, остальное $+\infty$
максимум	$-\infty$	старт — 0, остальное $-\infty$
логическое «или»	ложь	старт — истина, остальное ложь

Строка про количество выглядит противоречиво — «нейтральный ноль, а база единица». Противоречия нет: ноль ставится в недостижимые состояния, а единица — в начальное, потому что дойти до старта можно ровно одним способом, ничего не делая.

Проверять базу надо не рассуждением, а руками: посчитайте ответ для $n = 0$, $n = 1$, $n = 2$ на бумаге и сравните с тем, что выдаёт код. Это тридцать секунд и половина отловленных ошибок.

Недостижимые состояния

Задача: набрать сумму $S$ монетами номиналов $c_1, \dots, c_k$, каждый можно брать сколько угодно раз, минимизируя число монет.

const long long INF = 1e18;
vector<long long> d(S + 1, INF);
d[0] = 0;
for (int s = 1; s <= S; s++)
    for (int c : coins)
        if (c <= s && d[s - c] != INF)
            d[s] = min(d[s], d[s - c] + 1);

cout << (d[S] == INF ? -1 : d[S]);

Проверено: на 5000 наборах (в 1395 из них сумма недостижима) совпадает с поиском в ширину по достижимым суммам.

Соблазн — не заводить бесконечность, а оставить в недостижимых состояниях ноль. Замер: на 793 наборах из 5000 это даёт неверный ответ. Причина в том, что ноль — правдоподобное значение: оно не отличается от «сумму можно набрать нулём монет», и ошибка расползается по всей таблице.

Проверка d[s - c] != INF тоже не формальность. Без неё в таблицу попадёт $\text{INF} + 1$, потом $\text{INF} + 2$, и при неудачном выборе константы получится переполнение со сменой знака — бесконечность станет большим отрицательным числом и выиграет минимум.

Отсюда практическое правило выбора константы: бесконечность должна пережить все прибавления, которые к ней применят. Для long long берите $10^{18}$, а не LLONG_MAX: запас в девять порядков переживает любое разумное число сложений.

Порядок обсчёта

Порядок верен, если в момент вычисления состояния все, от которых оно зависит, уже посчитаны. Проверяется механически: выпишите формулу и посмотрите на индексы.

Если в формуле для $d[i][j]$ стоят только $d[i-1][\cdot]$ и $d[i][j-1]$ — годится обход по строкам сверху вниз, слева направо. Если встречается $d[i][j+1]$ — по строке надо идти справа налево. Если встречается и то и другое — обычного обхода нет, и надо либо менять состояние, либо считать лениво.

Самый заметный пример того, как порядок меняет смысл, — рюкзак:

for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)             // по убыванию
        d[j] = max(d[j], d[j - w[i]] + c[i]);

Поменяйте j-- на j++ — и решение не сломается, а начнёт решать другую задачу: каждый предмет можно будет взять сколько угодно раз.

Проверено: на 20 000 наборов цикл по возрастанию дал ответ, отличный от правильного, в 8055 случаях — и во всех 20 000 совпал с неограниченным рюкзаком. Это не сбой, это ровно другая постановка.

Такие ошибки опаснее всего: код проходит примеры из условия (там предметы часто и так берутся по одному разу) и падает на середине тестов.

Чем ловить

Маленький случай руками. $n = 0, 1, 2$. Ловит базу.

Стресс-тест против перебора. Пишется за десять минут, ловит и базу, и порядок, и переход. Для динамики он особенно уместен: перебор пишется почти всегда, а расхождение находится на массиве из четырёх элементов, где видно глазами.

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

Санитайзер. -fsanitize=address,undefined ловит выход за границы массива при отрицательных индексах — самую частую поломку в переходах. Подробнее — в статье об отладке.