Динамическое программирование — Стратегия подхода к вопросу DP

Динамическое программирование — стратегия подхода к вопросу DP

Динамическое программирование — это улучшение по сравнению с рекурсией!!!

DP == Рекурсия + Мемоизация (сверху вниз) или табуляция (снизу вверх)

Определить DP

Ищите ключевые слова, такие как максимальное, минимальное, количество способов или оптимальное. Еще одна подсказка будет заключаться в том, что у нас есть разные варианты/альтернативы на каждом этапе. Затем поищите ответ на вопрос: является ли данная проблема задачей оптимизации?

Оптимальная подструктура.Данная проблема обладает свойством оптимальной подструктуры, если оптимальное решение данной проблемы может быть получено с использованием оптимальных решений ее подзадач. Предположим, мы хотим найти кратчайший путь от Источника до Назначения. Пусть Via будет промежуточной точкой между A и Source с одно ребро, соединяющее его с Источником. Но у нас есть несколько путей от Via до Destination. В этом случае shortest(source, destination) = min(Source → Via + min(Via → Destination)).

Перекрывающаяся подзадача. Динамическое программирование объединяет решения подзадач, которые требуются снова и снова. DP сохраняет результаты подзадач, чтобы избежать повторных вычислений.

Увидев вопрос, выполните следующие действия:

Визуализируйте проблему
Найти подзадачу (суффикс, префикс, подстрока)
Найдите взаимосвязь между подзадачами
Обобщить отношения
Реализовать порядок подзадач

После того, как вы собрали наблюдения, используйте следующую структуру для решения проблемы.

Давайте возьмем вопрос, чтобы понять весь процесс, описанный выше.

Поднимаясь по лестнице

Вы поднимаетесь по лестнице. Требуется n шагов, чтобы добраться до вершины. Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколько различных способов вы можете подняться на вершину?

Фреймворк для решения задач DP

1. Определите целевую функцию

f(n) — количество различных способов подняться на n-ю ступеньку.

2. Определите наименьшие допустимые входные данные для базовых случаев.

f(0) = 1
f(1) = 1
f(2) = 2 # f(2) can be caluculated from f(0) and f(1) as well. I have taken this just for more clarity.

3. Запишите рекуррентное соотношение для целевой функции.

f(n) = f(n-1) + f(n-2)

Примечание. В рекурсии мы обычно уменьшаем пространство ввода при каждом последующем вызове функции. Здесь мы уменьшаем n, если у нас есть массив, либо мы уменьшаем размер массива, либо увеличивая индекс (слева направо), либо уменьшая индекс (справа налево).

4. Каков порядок выполнения?

n → n-1 → n-2 … 1 → 0

5. Где искать ответ?

f(n)

Рекурсивное решение

class Solution:
    def climbStairs(self, n):
        return self.cs_helper(n)
    
    def cs_helper(self, n): 
        if n == 0: 
           return 0
        if n == 1:
           return  1
        if n == 2:
           return 2
        
        return self.cs_helper(n - 1) + self.cs_helper(n - 2)

Рекурсия + мемоизация

Тот, кто не может вспомнить прошлое, обязан его повторить.

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

class Solution:
    def climbStairs(self, n):
        memo = [None for i in range(n + 1)]
        return self.cs_helper(n, memo)
    
    def cs_helper(self,n,memo):
        if memo[n] is not None:
            return memo[n] 
        if n == 0: 
           return 0
        if n == 1:
            result =  1
        if n == 2:
            result = 2
        else:
            result = self.cs_helper(n - 1, memo) + self.cs_helper(n - 2, memo)
            memo[n] = result
        return result

Примечание. Вам не нужно реализовывать рекурсивную функцию, вы можете просто придумать рекурсивную математическую функцию и найти ее состояния, а затем перейти к созданию метрики/массива состояний.

Когда у нас есть решение сверху вниз, мы можем преобразовать его в решение табуляции.

Снизу вверх / Табуляция

Теперь мы преобразуем рекурсивное решение в линейное, следуя структуре. Поскольку в базовом случае мы использовали 0, 1 и 2 второго шага, мы инициализируем dp[0], dp[1] и dp[2] значениями 0, 1, 2. Вызовы функций изменяются на dp[n ] присваивание, которое использует две последние позиции (dp[n-1] и dp[n-2]) в качестве поиска для получения ответа.

class Solution:
    def climbStairs(self, n):
        dp = [0] * (n+1)
        dp[0], dp[1], dp[2] = 0, 1, 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

В приведенном выше решении мы использовали порядок 0 → 1 → 2 → 3… → n-1 → n.

Оптимизация пространства в DP

Поскольку в каждом индексе мы ищем только два последних значения, мы можем удалить массив DP и использовать только две переменные для получения результата.

class Solution:
    def climbStairs(self, n):
        first = 1
        second = 1
        for i in range(2, n+1):
            res = first+second
            first, second = second, res
        return second

Основное различие между подходом Сверху вниз и снизу вверх заключается в том, что в последнем вычисляются все решения, а в первом вычисляются только те, которые требуются. В подходе «снизу вверх» (таблица) мы можем оптимизировать пространственную сложность, что невозможно в рекурсивном решении.

Временная сложность = O(количество состояний * время, необходимое для вычисления одного состояния)

Bottom-Up обычно быстрее, потому что рекурсия требует значительных вычислительных затрат.
Метод «сверху вниз» работает быстрее в тех случаях, когда существует множество состояний таблицы, которые никогда не рассчитываются.

Удачного кодирования!!!

Динамическое программирование — Стратегия подхода к вопросу DP