Восстановление ответа

Таблица динамики знает значение ответа, но не сам ответ: какие предметы взяты, каким путём шли, какая подпоследовательность выбрана. Восстанавливается это двумя способами.

Способ первый: массив предков

При каждом обновлении состояния запоминаем, откуда пришли.

vector<int> d(n, 1), from(n, -1);
int best = 0, bestIndex = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
        if (a[j] < a[i] && d[j] + 1 > d[i]) {
            d[i] = d[j] + 1;
            from[i] = j;                        // запомнили предка
        }
    if (d[i] > best) { best = d[i]; bestIndex = i; }
}

vector<int> answer;
for (int i = bestIndex; i != -1; i = from[i]) answer.push_back(a[i]);
reverse(answer.begin(), answer.end());

Проверено: на 20 000 случайных массивах до 14 элементов восстановленная последовательность возрастает, является подпоследовательностью исходного массива и имеет ту же длину, что даёт динамика.

Способ прямолинейный и стоит дополнительной памяти под массив той же формы, что и таблица. Для двумерной динамики это заметно: к таблице $10^3 \times 10^5$ второй такой массив уже не приставишь.

Способ второй: пересчёт по таблице

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

int i = n - 1, j = m - 1;
string path;
while (i != 0 || j != 0) {
    if (i > 0 && d[i][j] == d[i - 1][j] + a[i][j]) { path += 'D'; i--; }
    else                                          { path += 'R'; j--; }
}
reverse(path.begin(), path.end());

Памяти не тратится вовсе, времени — длина ответа. Так делают почти всегда, когда таблица целиком помещается в память.

Ограничение у способа одно, зато существенное: он несовместим с экономией памяти. Если от таблицы остались две строки, восстанавливать не по чему.

Лексикографический минимум

Условие часто добавляет: «если ответов несколько, выведите лексикографически наименьший». Здесь легко потерять баллы на ровном месте.

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

В примере выше ходы обозначены D и R, и D меньше. Поэтому проверка «можно ли пойти вниз» стоит первой, а R берётся, только когда вниз оптимума не даёт.

Проверено: на 20 000 досках до $5 \times 5$ такая процедура совпадает с полным перебором маршрутов, выбирающим минимальную сумму, а среди равных — лексикографически меньшую запись ходов.

Частая ошибка — восстанавливать с конца и в конце развернуть, продолжая брать «меньший символ». Так получается лексикографический минимум перевёрнутой строки, а это не то же самое. Если восстанавливать приходится с конца, идите жадно от начала по готовой таблице, как в коде выше, или считайте динамику в обратную сторону.

Сколько всего оптимальных ответов

Отдельная просьба в условиях: посчитать число оптимальных решений. Делается второй таблицей, которая считается вместе с первой.

if (candidate < d[i]) { d[i] = candidate; cnt[i] = cnt[j]; }
else if (candidate == d[i]) cnt[i] += cnt[j];

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

Числа здесь растут быстро, так что в условии почти наверняка будет «по модулю $10^9 + 7$» — арифметика по модулю со всеми её обычными предосторожностями.