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

В этих решениях мы строим двумерный массив размером N * M (представляющий таблицу из N * M ячеек), где N - количество предметов, из которых мы можем выбрать, а M - количество единиц вместимости нашего рюкзака.

Сегодня я опишу, как эти решения можно оптимизировать для использования только одномерного массива. Вы можете думать об этой оптимизации как об уменьшении сложности пространства с O (NM) до O (M), где N - количество элементов, и M количество единиц вместимости нашего ранца.

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

В этих задачах мы используем DP, чтобы оптимизировать наше решение по времени (рекурсивный подход) за счет пространства. Мы храним решения подзадач, чтобы впоследствии использовать их, не пересчитывая их.

Оптимизация для использования пространства: шаг 1

Однако если вы внимательно изучите алгоритм, вы заметите, что мы используем только очень конкретную часть таблицы на каждом этапе.

Например, рассмотрим строки 4–13:

Обратите внимание, что мы проверяем только значения в предыдущей строке. Другими словами, если мы сейчас находимся в строке 15, нам нужны только значения в строке 14. Строки 1–13 совершенно неактуальны (они были релевантными назад, когда заполнялась строка, непосредственно следующая за ними, но они мгновенно потеряли свою актуальность после того, как это произошло).

Следовательно, нам действительно нужно поддерживать только 2 строки в любое время: одну для представления предыдущей строки, а другую для представления текущей строки.

Это немедленно снижает сложность пространства с O (NM) до O (M).

Оптимизация для использования пространства: шаг 2

В этот момент внимательный читатель мог бы подумать:

«Неужели нам действительно нужны 2 ряда?» (Если это вы, отличная работа! Мне потребовалась целая вечность, чтобы понять эту оптимизацию, даже когда я читал рабочий код, так что, если вы заметили это сразу, это действительно здорово.)

На самом деле нет! Если вы внимательно прочитаете строки 7–13 (приведенного выше фрагмента), вы поймете, что мы используем только определенную часть предыдущей строки. В частности, мы используем только ту часть, которая находится непосредственно вверху и слева (т.е. номер столбца ≤ номер текущего столбца).

Следовательно, можно поддерживать только 1 строку (то есть одномерный массив) на протяжении всего алгоритма.

Слева направо или справа налево?

Чтобы это сработало, мы не можем строить нашу строку слева направо. Это приведет к перезаписи информации, которая нам впоследствии понадобится. На каждом этапе вычисления значения ячейки в строке нам требуются значения ячеек в предыдущей строке , но только слева.

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

Меньше разговоров, больше кода

Может быть сложно визуализировать объяснение, не читая код. Вот приведенное выше решение, переписанное после обоих этапов оптимизации.

Это действительно помогает выполнить алгоритм в IDE шаг за шагом - именно так я усвоил этот изящный трюк. Честно говоря, эта оптимизация не очень важна, поскольку мы, как правило, больше озабочены временной сложностью, но, тем не менее, это действительно круто.