Это концепция программирования, которая доставила мне много трудностей, когда я ее изучал. Мой стиль программирования очень визуален, в том смысле, что я должен визуализировать проблему, прежде чем смогу ее решить. Динамическое программирование довольно устойчиво к этому методу или любому интуитивному пониманию. На самом деле, даже решения трудно уложить в голове (и мы поймем, почему).
Что ж, я утверждаю, что большинство решений и методов, которые вы найдете в Интернете, основаны на заранее подготовленной логике, которая успешно генерирует правильный ответ, но не раскрывает, как на самом деле работает динамическое программирование. Я утверждаю, что оптимальное решение (наилучшее для временной и пространственной сложности) на самом деле легче всего понять.
Общепринятая практика заключается в переносе решения в эти гигантские массивы и возврате последнего элемента. Я потратил, наверное, день, пытаясь понять, почему ты это делаешь. Что ж, оказывается, это не делает ничего, кроме увеличения сложности памяти и сбивает с толку всех, кто пытается понять, как на самом деле работает динамическое программирование.
Тогда есть рекурсивные методы. Для меня рекурсия имеет смысл в обходе графа (и дерева), но мне трудно визуализировать ее и отслеживать логику конкретно для задач DP. Это также оказывается наименее оптимальным решением с точки зрения временной и пространственной сложности. Да, его можно улучшить с помощью кэширования, но итеративное восходящее решение всегда лучше (и, как мы увидим, оно также легче для понимания).
Я продемонстрирую на очень простом примере. Найдите максимальную последовательную сумму следующего массива:
[-1, 2, 3, 4, -2]
Решение в этом случае равно 9 (сумма 2,3,4). Подход грубой силы очень прост; просто найдите максимальную сумму всех возможных последовательных подмассивов… очевидно, это не то решение, которое нам нужно, поскольку временная сложность квадратична. Итак, как мы это визуализируем?
Один ключевой момент, который важно признать, заключается в том, что динамическое программирование — это метод решения проблем, которые можно разбить на подзадачи. Итак, какова первая подзадача?
[-1, 2]
Это первая подзадача. И мы всегда хотим оценивать задачи динамического программирования в обратном направлении! Поскольку нам нужно линейное решение O (n), при построении цикла мы должны начать с 2 (i = 1), потому что мы будем оценивать против -1 (i-1). Почему не наоборот? Ну, если подумать, если мы начнем с 2 и оценим в обратном направлении, мы имеем дело с самодостаточной проблемой. Каждая итерация не должна знать о будущих итерациях; это концептуально эквивалентно работе с каждым подмассивом за раз на каждой последовательной итерации. Если мы начнем наш цикл с -1 (i=0) и оценим вперед, тогда нет подзадачи, которую можно решить.
Итак, давайте решим эту подзадачу, чтобы построить нашу логику. Если мы рассмотрим [-1,2], максимальная последовательная сумма равна 2. Как мы решим это алгоритмически?
2 > -1+2 > -1
Наибольшее значение между 2, -1+2 и -1 равно 2. Таким образом, дальнейшее решение состоит в том, чтобы сохранить (или кэшировать) 2 и оценить его на следующей итерации. Хорошо, а теперь самое интересное… как мы это визуализируем? Я называю это каскадным методом:
Посмотрите внимательно на то, что мы делаем. Решение первой подзадачи равно 2, и мы сохраняем его в кэшированной переменной. Теперь, переходя к i=2 (3), мы применяем ту же логику, и наше кэшированное значение становится равным 5 (поскольку 3+2 больше 2 и больше 3). Переходя к i=3 (4), наша логика дает нам 9 и, наконец, переходя к i=4 (-2), наша логика дает нам 7 (-2 + 9). А поскольку 7 меньше 9, оно не устанавливается в качестве нашей кешированной переменной.
Наш цикл заканчивается, и у нас остается 9… правильное решение. Итак, как видите, нет причин хранить более одного значения в нашей кэшированной переменной. Нет никакой логической причины хранить 2,5,9 в массиве и возвращать последнее значение (9). На данный момент это должно быть довольно очевидно, но большинство принятых решений будут делать именно это.
Поэтому, если вы застряли в расшифровке решений динамического программирования, вы должны знать, что эти решения часто излишне сложны и трудны для понимания. На мой взгляд, чтобы действительно понимать динамическое программирование, мы должны знать, что мы кешируем и зачем (и кешируем только то, что необходимо). В следующем посте мы закодируем это и рассмотрим более сложные примеры.
