Ну, чтобы решить любую проблему динамического программирования, вам нужно разбить ее на повторяющиеся подрешения.
Скажем, мы определили вашу проблему как A (n, k), которая возвращает наибольшее возможное число, удаляя k цифр из n.
Из этого можно определить простой рекурсивный алгоритм.
Используя ваш пример, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}
В общем, A (n, k) = max {A (n с удаленной 1 цифрой, k - 1)}
И ваш базовый случай: A (n, 0) = n.
Используя этот подход, вы можете создать таблицу, которая кэширует значения n и k.
int A(int n, int k)
{
typedef std::pair<int, int> input;
static std::map<input, int> cache;
if (k == 0) return n;
input i(n, k);
if (cache.find(i) != cache.end())
return cache[i];
cache[i] = /* ... as above ... */
return cache[i];
}
Теперь это прямое решение, но есть лучшее решение, которое работает с очень маленьким одномерным кэшем. Попробуйте перефразировать вопрос следующим образом: «Учитывая строку n и целое число k, найдите лексикографически наибольшую подпоследовательность в n длины k». По сути, это ваша проблема, а решение гораздо проще.
Теперь мы можем определить другую функцию B (i, j) , которая дает наибольшую лексикографическую последовательность длины (i - j) , используя только первую i цифр n (другими словами, удалив j цифр из первых i цифр n ).
Снова используя ваш пример, мы получили бы:
B (1, 0) = 1
B (2, 0) = 12
B (3, 0) = 123
B (3, 1) = 23
B (3, 2) = 3
и т.д.
Немного подумав, мы можем найти отношение повторения:
B (i, j) = макс. (10B (i-1, j) + n i , B (i-1, j-1))
или, если j = i , то B (i, j) = B (i-1, j-1)
и B (0, 0) = 0
И вы можете закодировать это так же, как описано выше.