Почему мемоизация рекурсии иногда даёт WA из-за неинициализированного «пустого» значения?
Делаю top-down ДП с массивом memo, инициализирую его -1 как «не посчитано». Но в задаче само значение ответа может быть -1 (или 0), и кэш ломается: посчитанное -1 воспринимается как «не посчитано» и пересчитывается, иногда с WA. Как правильно?
2 ответа
Классическая ошибка: сентинел «не посчитано» совпал с возможным валидным ответом. Решения:
- Возьми сентинел заведомо вне диапазона ответа. Если ответ может быть
-1, инициализируйmemoзначением, которого ответ принять не может (напримерINT_MINили специально выбранное-2e9). - Отдельный флаг «посчитано». Самый надёжный — массив
bool computed[...](илиvector<bool>), не завязанный на значение:
int solve(int i) {
if (computed[i]) return memo[i];
computed[i] = true;
int res = /* ... рекурсия ... */;
return memo[i] = res;
}
Флаг ставим до рекурсивных вызовов в задачах с возможной цикличностью состояний, чтобы не зациклиться. Это убирает зависимость корректности кэша от диапазона значений.
Сложность не меняется — флаг добавляет O(states) памяти. Зато уходит коварный WA, который воспроизводится только когда настоящий ответ равен сентинелу.
Ещё одна засада в той же области — memset(memo, -1, ...) для не-char типов. memset пишет побайтово, и -1 корректно заполняет int всеми единицами (получается -1), но если попробуешь memset(..., 0x3f, ...) для INF — получишь 0x3f3f3f3f (≈10^9), что удобно как «бесконечность» именно потому, что INF+INF не переполняет int. А вот memset(memo, 1, ...) НЕ даст 1 в каждом int (даст 0x01010101). Поэтому для произвольных значений инициализации используй fill/std::fill, а memset — только для 0, -1 и трюка 0x3f.