Учебник по динамическому программированию: создание эффективных программ на Python

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

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

Чтобы помочь вам перейти к эффективному коду Python, вот краткое руководство о том, что такое динамическое программирование, почему оно более эффективно и как использовать его для решения распространенных задач собеседования.

Что такое динамическое программирование?

Динамическое программирование — это метод решения сложных проблем путем рекурсивного разбиения их на подзадачи, каждая из которых затем решается индивидуально. Динамическое программирование оптимизирует рекурсивное программирование и экономит время на повторное вычисление входных данных позже.

Это отличается от техники » Разделяй и властвуй» тем, что подзадачи в решениях динамического программирования перекрываются, поэтому некоторые из одинаковых шагов, необходимых для решения одной подзадачи, также необходимы для других подзадач.

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

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

Почему динамическое программирование эффективно? Рекурсия против DP

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

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

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

Примеры динамического программирования

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

В отличие от компьютеров, процессы, основанные на памяти, такие как динамическое программирование, интуитивно понятны людям. Рассмотрим этот пример из реальной жизни:

Представьте, что вы хотите пойти в новый продуктовый магазин через несколько улиц, но не знаете, как туда добраться. Чтобы решить подзадачу маршрута к магазину, вы просматриваете маршруты на карте вашего смартфона, а затем направляетесь туда.

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

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

По сути, это то, как динамическое программирование работает и в программах.

Факторная проблема

Мы можем увидеть в реальной жизни, насколько динамическое программирование более эффективно, чем рекурсия, но давайте посмотрим, как это работает с кодом Python!

Ниже у нас есть два решения, которые находят число Фибоначчи для заданного входа, а затем показывают график времени выполнения программы. Левая вкладка представляет собой простую рекурсию грубой силы, а правая вместо этого использует динамическое программирование.

Посмотрите на разницу.

Recursion

import time

import matplotlib.pyplot as plt

def fib(n):

  if n <= 0: # base case 1

    return 0

  if n <= 1: # base case 2

    return 1

  else: # recursive step

    return fib(n-1) + fib(n-2)

numbers = 20

DynamicProgramming

import time

import matplotlib.pyplot as plt

calculated = {}

def fib(n):

  if n == 0: # base case 1

    return 0

  if n == 1: # base case 2

    return 1

  elif n in calculated:

    return calculated[n]

  else: # recursive step

    calculated[n] = fib(n-1) + fib(n-2)

    return calculated[n]

showNumbers = False

numbers = 20

Как видите, в код динамического решения мы добавили возможность сохранять старые результаты (строка 12) перед переходом к следующему рекурсивному шагу (строки 13-15). Позже в статье мы увидим более сложные динамические решения и их пошаговую разбивку.

Обратите внимание при сравнении каждого графика, как почти линейная временная сложность, На)О ( п ), динамического решения заставляет его работать намного лучше даже на более поздних числах по сравнению с квадратичной временной сложностью рекурсивной функции О (2 ^ п)O ( 2​п​​).

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

Не все динамические решения работают одинаково. Некоторые строятся снизу вверх, а другие — сверху вниз. Различие можно найти в том, как каждый начинает задачу и как хранятся результаты подзадач.

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

Что такое табуляция?

Табулирование — это процесс последовательного сохранения результатов подзадач восходящего подхода.

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

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

Нисходящее динамическое программирование

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

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

Что такое мемоизация?

Мемоизация — это процесс хранения результатов подзадач по принципу «сверху вниз».

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

В Python это лучше всего достигается с помощью структуры данных словаря, потому что мы можем использовать ее для хранения неупорядоченных данных с парами ключ / значение.

Примеры динамического программирования: снизу вверх или сверху вниз

Чтобы лучше понять различия между этими схемами, давайте посмотрим, как мы переработали бы наш пример Фибоначчи как снизу вверх, так и сверху вниз.

BottomUpTab

TopDownMem

memo = {} #dictionay for Memoization

def fib(n):

  if n == 0: # base case 1

    return 0

  if n == 1: # base case 2

    return 1

  elif n in memo: # Check if result for n has already been evaluated

    return memo[n] # return the result if it is available

  else: # otherwise recursive step

    memo[n] = fib(n-1) + fib(n-2) # store the result of n in memoization dictionary

    return memo[n] # return the value

print (fib(100))

Практика задач динамического программирования

А теперь попробуйте сами! Вот несколько практических вопросов, взятых из нашего интерактивного курса «Динамическое программирование в Python». Многие из этих проблем характерны для собеседований по программированию для проверки ваших навыков динамического программирования. Знакомство с этими проблемами сделает вас лучшим кандидатом.

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

Проблема с рюкзаком

Постановка задачи:

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

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

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

Примеры входных данных:

weights = [1, 2, 4, 6]

prices = [4, 2, 4, 7]

capacity = 7

def solveKnapsack(weights, prices, capacity, index, memo):

  # base case of when we have run out of capacity or objects

  if capacity <= 0 or index >= len(weights):

    return 0

  # check for solution in memo table

  if (capacity, index) in memo:

    return memo[(capacity, index)]

  # if weight at index-th position is greater than capacity, skip this object

  if weights[index] > capacity:

    # store result in memo table

    memo[(capacity, index)] = solveKnapsack(weights, prices, capacity, index + 1, memo)

    return memo[(capacity, index)]

  # recursive call, either we can include the index-th object or we cannot, we check both possibilities and return the most optimal one using max

  memo[(capacity, index)] = max(prices[index]+solveKnapsack(weights, prices, capacity — weights[index], index+1, memo),

        solveKnapsack(weights, prices, capacity, index + 1, memo))

  return memo[(capacity, index)]

def knapsack(weights, prices, capacity):

  # create a memo dictionary

  memo = {}

  return solveKnapsack(weights, prices, capacity, 0, memo)

print(knapsack([2,1,1,3], [2,8,1,10], 4))

Разбивка решения:

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

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

Проблема с разменом монет

Это вариант «проблемы размены монет», который часто задают на собеседованиях по кодированию.

Постановка задачи:

Имея список денежных купюр, вам необходимо подсчитать количество способов, которыми вы можете представить определенную сумму. Например, если у вас есть только два вида счетов, 10 и 20 долларов, и вы хотите представить 30 долларов, есть только два способа:

• 3 купюры по 10 долларов
• 1 купюра на 20 долларов и 1 купюра на 10 долларов.

При разработке алгоритма будьте особенно осторожны, чтобы не переоценить. 30 долларов могут быть представлены как 20 + 10 долларов, а также 10 + 20 долларов, но это одно и то же. Следовательно, не стоит рассчитывать оба случая.

Простое рекурсивное решение приведет к тайм-ауту для больших входных данных; таким образом, вы должны попытаться написать алгоритм динамического программирования. Начните с рекурсивного решения и создайте динамическое решение.

Workspace

def knapsack(weights, prices, capacity):

  # your code goes here

  return 0

Solution

def countways_(bills, amount, index):

  if amount == 0:     # base case 1

    return 1

  if amount < 0 or index >= len(bills):      # base case 2

    return 0

  # count the number of ways to make amount by including bills[index] and excluding bills[index]

  return countways_(bills, amount — bills[index], index) + countways_(bills, amount, index+1)

def countways(bills, amount):

  return countways_(bills, amount, 0)

print(countways([1,2,5], 5))

Рекурсивный анализ решения:

Найти разные комбинации в наборе вещей несложно. Фактически, одна из первых задач, которые мы решали в этом курсе, заключалась в поиске различных перестановок строки. Сложность заключалась в том, как избежать переоценки из-за тех же перестановок.

Например, 10 + 20 долларов прибавляются к 30 долларам, так же как и 20 + 10 долларов. В контексте перестановок обе эти последовательности будут разными, но в случае комбинаций это одно и то же, что означает, что мы не должны пересчитывать их дважды. Мы достигаем этого, ограничивая каждый рекурсивный вызов для использования подмножества счетов.

Ключевой частью этого решения является сумма двух рекурсивных вызовов в строке 7. Чтобы подсчитать сумму, некоторые комбинации либо будут включать конкретный счет, предоставленный, bills[index]либо нет. Итак, мы можем просто посчитать обе эти возможности. Первый вызов countways_считается bills[index]частью решения, тогда как второй вызов пропускает его. Давайте посмотрим на простую визуализацию этого алгоритма.

Workspace

# dynamic solution

def countways(bills, amount):

  # write your code here

  return 0

Solution

def countways(bills, amount):

  if amount <= 0:

    return 0

  dp = [[1 for _ in range(len(bills))] for _ in range(amount + 1)]

  for amt in range(1, amount+1):

    for j in range(len(bills)):

      bill = bills[j]

      if amt — bill >= 0:

        x = dp[amt — bill][j]

      else:

        x = 0

      if j >= 1:

        y = dp[amt][j-1]

      else:

        y = 0

      dp[amt][j] = x + y

  return dp[amount][len(bills) — 1]

print(countways([1,2,5], 5))

Разбивка динамического решения:

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

Чтобы получить сумму, используя n купюр, нам просто нужно подсчитать способы, которыми мы можем заработать сумму, используя n- ю купюру (строки 8–9) или не используя ее (строки 12–13). Алгоритм легче понять с визуализацией, представленной ниже.

Заключение и ресурсы

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

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