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

![](ru/docs/assets/media/image836.jpeg){width="3.2760411198600177in" height="4.239583333333333in"}

1.  **введение в динамичеСкОе прОграммирОвание** *Динамическое программирование* является важной парадигмой в алгоритмах. Ее суть заключается в разбиении задачи на серию более мелких подзадач. Со-

> хранение решений подзадач позволяет избежать повторных вычислений, что значительно повышает временную эффективность.
>
> В этом разделе мы начнем с классического примера и сначала представим его решение методом перебора. Мы понаблюдаем за наличием перекрыва- ющихся подзадач, а затем постепенно выведем более эффективное решение с использованием динамического программирования.
>
> Как показано на рис. 14.1, для лестницы с тремя ступенями существует три способа добраться до вершины.
>
> ![](ru/docs/assets/media/image838.jpeg)Количество ступеней **n** =

Есть 3 способа подняться на **3-ю** ступень:

> **Рис. 14.1.** Количество способов добраться до 3-й ступени
>
> Цель этой задачи -- найти количество способов, **и можно попробовать использовать для ее решения метод поиска с возвратом**. Более конкрет- но -- можно представить подъем по лестнице как процесс многократного выбора: начать с пола, на каждом этапе выбирать подъем на одну или две ступени, при достижении вершины лестницы количество способов увели- чивается на 1, а при превышении вершины происходит обрезка. Ниже при- веден код реализации.
>
> \# === File: climbing_stairs_backtrack.py ===
>
> def backtrack(choices: list\[int\], state: int, n: int, res: list\[int\]) -\> int: \"\"\" Поиск с возвратом.\"\"\"
>
> \# Когда достигнута n-я ступень, количество способов увеличивается на 1. if state == n:
>
> res\[0\] += 1
>
> \# Перебор всех вариантов. for choice in choices:
>
> \# Обрезка: не допускается превышение n-й ступени. if state + choice \> n:
>
> continue
>
> \# Попытка: сделать выбор, обновить состояние. backtrack(choices, state + choice, n, res)
>
> \# возврат.
>
> def climbing_stairs_backtrack(n: int) -\> int:
>
> \"\"\" Подъем по лестнице: поиск с возвратом.\"\"\"
>
> choices = \[1, 2\] \# Можно выбрать подъем на 1 или 2 ступени. state = 0 \# Начало подъема с 0-й ступени.
>
> res = \[0\] \# Используется res\[0\] для записи количества способов. backtrack(choices, state, n, res)
>
> return res\[0\]

### Первый метод: полный перебор

> Алгоритм поиска с возвратом обычно не разбивает задачу явным образом, а рассматривает ее решение как серию шагов принятия решений, исследуя пути обхода и выполняя обрезку.
>
> Можно попытаться проанализировать эту задачу с точки зрения разбиения. Пусть для достижения *i*-й ступени существует *dp*\[*i*\] способов, тогда *dp*\[*i*\] являет- ся исходной задачей, а ее подзадачи включают следующие:
>
> *dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i* − 2λϑ , \... *, dp* ℘Λ2λϑ , *dp* ℘Λ1λϑ .
>
> На каждом этапе можно подниматься только на одну или две ступени, поэто- му перед на *i*-й ступенью мы находились либо на (*i* -- 1)-й, либо на (*i* -- 2)-й сту- пени. Другими словами, на *i*-ю ступень можно перейти только с (*i* -- 1)-й или (*i* -- 2)-й ступени.
>
> Отсюда следует важный вывод: **количество способов добраться до** (*i* -- 1)-**й ступени плюс количество способов добраться до** (*i* -- 2)-**й ступени равно количеству способов добраться до** *i*-**й ступени**. Формула выглядит сле- дующим образом:
>
> *dp* ℘Λ*i* λϑ *= dp* ℘Λ*i* −1λϑ + *dp* ℘Λ*i* −1λϑ .
>
> Это означает, что в задаче подъема по лестнице между подзадачами суще- ствует рекуррентная зависимость, и **решение исходной задачи можно по- строить из решений подзадач**. На рис. 14.2 демонстрируется эта рекуррент- ная зависимость.
>
> ![](ru/docs/assets/media/image840.jpeg)
>
> **Рис. 14.2.** Рекуррентная зависимость количества способов подъема по лестнице
>
> Можно получить решение методом полного перебора на основе рекуррент- ной формулы. Начиная с *dp*\[*n*\], **большая задача рекурсивно разбивается на сумму двух меньших задач**, пока не будут достигнуты минимальные под- задачи *dp*\[1\] и *dp*\[2\], для которых возвращаются известные решения: *dp*\[1\] = 1, *dp*\[2\] = 2. То есть для достижения 1-й и 2-й ступеней существует 1 и 2 способа соответственно.
>
> Рассмотрим следующий код, который, как и стандартный код поиска с воз- вратом, относится к поиску в глубину, но является более лаконичным.
>
> \# === File: climbing_stairs_dfs.py === def dfs(i: int) -\> int:
>
> \"\"\" Поиск.\"\"\"
>
> \# dp\[1\] и dp\[2\] известны, возврат. if i == 1 or i == 2:
>
> return i
>
> \# dp\[i\] = dp\[i-1\] + dp\[i-2\] count = dfs(i - 1) + dfs(i - 2) return count
>
> def climbing_stairs_dfs(n: int) -\> int: \"\"\" Подъем по лестнице: поиск.\"\"\" return dfs(n)
>
> На рис. 14.3 изображено рекурсивное дерево, образованное полным перебо- ром. Для задачи *dp*\[*n*\] глубина рекурсивного дерева равна *n*, а временная слож- ность составляет *O*(2*n*). Экспоненциальный рост приводит к взрывному увели- чению, и при вводе достаточно большого *n* можно столкнуться с длительной работой алгоритма.
>
> ![](ru/docs/assets/media/image842.jpeg)
>
> **Рис. 14.3.** Рекурсивное дерево для подъема по лестнице
>
> Как видно из рис. 14.3, **экспоненциальная временная сложность вызва- на перекрывающимися подзадачами**. Например, *dp*\[9\] разбивается на *dp*\[8\] и *dp*\[7\], *dp*\[8\] разбивается на *dp*\[7\] и *dp*\[6\] -- обе задачи содержат подзадачу *dp*\[7\]. Таким образом, в подзадачах содержатся более мелкие перекрывающиеся подзадачи, и большая часть вычислительных ресурсов тратится на их обработку.

### Второй метод: мемоизация поиска

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

1.  При первом вычислении *dp*\[*i*\] мы записываем результат в mem\[i\] для дальнейшего использования.

2.  Когда требуется повторно вычислить *dp*\[*i*\], мы можем напрямую полу- чить результат из mem\[i\], избегая повторной обработки.

> Код реализации представлен ниже.
>
> \# === File: climbing_stairs_dfs_mem.py === def dfs(i: int, mem: list\[int\]) -\> int:
>
> \"\"\" мемоизация поиска.\"\"\"
>
> \# dp\[1\] и dp\[2\] известны, возврат. if i == 1 or i == 2:
>
> return i
>
> \# Если существует запись dp\[i\], возвращаем ее значение. if mem\[i\] != -1:
>
> return mem\[i\]
>
> \# dp\[i\] = dp\[i-1\] + dp\[i-2\]
>
> count = dfs(i - 1, mem) + dfs(i - 2, mem) \# Запись dp\[i\].
>
> mem\[i\] = count return count
>
> def climbing_stairs_dfs_mem(n: int) -\> int:
>
> \"\"\" Подъем по лестнице: мемоизация поиска.\"\"\"
>
> \# В mem\[i\] хранится количество способов подняться на i-ю ступень, \# -1 означает отсутствие записи.
>
> mem = \[-1\] \* (n + 1) return dfs(n, mem)
>
> После внедрения запоминания все пересекающиеся подзадачи нужно вы- числить только один раз, что оптимизирует временную сложность до *O*(*n*), это является значительным скачком, см рис. 14.4.

![](ru/docs/assets/media/image845.jpeg)

> **Рис. 14.4.** Мемоизация поиска и соответствующее дерево рекурсии

### Третий метод: динамическое программирование

> **Мемоизация поиска -- это метод «сверху вниз»**: мы начинаем с исходной задачи (корневой узел) и рекурсивно разбиваем более крупные подзадачи на более мелкие, пока не достигнем минимальных подзадач с известным реше- нием (листовые узлы). Затем через возврат поэтапно собираем решения под- задач, чтобы построить решение исходной задачи.
>
> В отличие от этого подхода **динамическое программирование представ- ляет собой метод «снизу вверх»**: начиная с решения минимальных подза- дач, итеративно строится решение более крупных подзадач, пока не будет по- лучено решение исходной задачи.
>
> Поскольку динамическое программирование не включает этап возврата, оно реализуется с использованием циклов и итераций, без необходимости
>
> в рекурсии. В следующем коде мы инициализируем массив dp для хранения ре- шений подзадач, который выполняет ту же функцию запоминания, что и мас- сив mem в мемоизации поиска.
>
> \# === File: climbing_stairs_dp.py === def climbing_stairs_dp(n: int) -\> int:
>
> \"\"\" Подъем по лестнице: динамическое программирование.\"\"\"
>
> if n == 1 or n == 2: return n
>
> \# Инициализация таблицы dp для хранения решений подзадач. dp = \[0\] \* (n + 1)
>
> \# Начальное состояние: предустановка решения минимальных подзадач. dp\[1\], dp\[2\] = 1, 2
>
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
>
> dp\[i\] = dp\[i - 1\] + dp\[i - 2\] return dp\[n\]
>
> На рис. 14.5 иллюстрируется процесс выполнения приведенного выше кода.

![](ru/docs/assets/media/image848.jpeg)

> **Рис. 14.5.** Применение динамического программирования для подъема по лестнице
>
> Как и в алгоритмах поиска с возвратом, в динамическом программировании используется концепция состояния для обозначения определенной стадии ре- шения задачи. Каждое состояние соответствует подзадаче и соответствующе- му локальному оптимальному решению. Например, состояние задачи подъема по лестнице определяется текущей ступенью *i*.
>
> На основе этого можно обобщить часто используемые термины динамиче- ского программирования.

- Массив dp называется таблицей dp, *dp*\[*i*\] обозначает решение подзадачи, соответствующей состоянию *i*.

<!-- -->

- Состояния, соответствующие минимальным подзадачам (1-я и 2-я сту- пени лестницы), называются начальными состояниями.

- Рекуррентное соотношение *dp*\[*i*\] = *dp*\[*i* − 1\] + *dp*\[*i* − 2\] называется уравне- нием перехода состояния.

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

> Внимательный читатель может заметить, что, **поскольку** *dp*\[*i*\] **зависит только от** *dp*\[*i* − 1\] **и** *dp*\[*i* − 2\], **нам не нужно использовать целый мас- сив** *dp* **для хранения всех решений подзадач**, а достаточно использовать только две переменные для последовательного продвижения. Ниже приве- ден пример кода.
>
> \# === File: climbing_stairs_dp.py ===
>
> def climbing_stairs_dp_comp(n: int) -\> int:
>
> \"\"\" Подъем по лестнице: динамическое программирование с оптимизацией про- странства.\"\"\"
>
> if n == 1 or n == 2: return n
>
> a, b = 1, 2
>
> for \_ in range(3, n + 1): a, b = b, a + b
>
> return b
>
> Как видно из кода, за счет исключения использования массива dp простран- ственная сложность снижается с *O*(*n*) до *O*(*1*).
>
> В задачах динамического программирования текущее состояние часто за- висит только от ограниченного числа предыдущих состояний. В этом случае можно сохранить только необходимые состояния, чтобы сэкономить память. **Эта техника оптимизации пространства называется скользящие пере- менные или скользящий массив**.

1.  **Особенности задач динамического программирования**

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

> ложение на подзадачи -- это универсальный алгоритмический подход, кото- рый по-разному применяется в методах «разделяй и властвуй», динамическом программировании и поиске с возвратом.

- Алгоритм «разделяй и властвуй» рекурсивно делит исходную задачу на несколько независимых подзадач до самых минимальных и в процессе обратного хода объединяет решения всех подзадач.

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

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

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

### Оптимальная подструктура

> Чтобы лучше продемонстрировать концепцию оптимальной подструктуры, рассмотрим задачу о подъеме по лестнице с небольшими изменениями.
>
> Если стоимость на 1-й, 2-й и 3-й ступенях составляет 1, 10 и 1 соответствен- но, то минимальная стоимость подъема с пола на 3-ю ступень равна 2, как по- казано на рис. 14.6.

![](ru/docs/assets/media/image850.jpeg)

> **Рис. 14.6.** Минимальная стоимость подъема на 3-ю ступень
>
> Пусть *dp*\[*i*\] обозначает накопленную стоимость для подъема на *i*-ю ступень. Поскольку на *i*-ю ступень можно попасть только с (*i* -- 1)-й или (*i* -- 2)-й ступени, *dp*\[*i*\] может быть равен либо *dp*\[*i* − 1\] + *cost*\[*i*\], либо *dp*\[*i* − 2\] + *cost*\[*i*\]. Чтобы мини- мизировать расход, следует выбрать меньшее из двух значений:
>
> *dp* ℘Λ*i* λϑ *=* min(*dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i* − 2λϑ + *cost* Λ℘*i*λϑ .
>
> Этот пример иллюстрирует смысл *оптимальной подструктуры*: **оптималь- ное решение исходной задачи строится на основе оптимальных реше- ний подзадач**.
>
> Очевидно, что данная задача обладает оптимальной подструктурой: из двух оптимальных решений подзадач *dp*\[*i* − 1\] и *dp*\[*i* − 2\] выбирается лучшее, и на его основе строится оптимальное решение исходной задачи *dp*\[*i*\].
>
> Итак, имеет ли задача о подъеме по лестнице из предыдущего разде- ла оптимальную подструктуру? Цель этой задачи -- вычислить количество решений, что на первый взгляд является задачей подсчета. Но если пере- фразировать вопрос как вычисление максимального количества решений, то неожиданно обнаруживается, что, **хотя модифицированная задача эк- вивалентна**, **возникает оптимальная подструктура**: максимальное ко- личество решений для *n*-й ступени равно сумме максимального количества решений для (*n* -- 1)-й и (*n* -- 2)-й ступеней. Таким образом, интерпретация оптимальной подструктуры может быть гибкой и иметь различное значение в зависимости от задачи.
>
> Согласно уравнению перехода состояния и начальному состоянию *dp*\[1\] = *cost*\[1\] и *dp*\[2\] = *cost*\[2\], можно получить код реализации динамического про- граммирования.
>
> \# === File: min_cost_climbing_stairs_dp.py ===
>
> def min_cost_climbing_stairs_dp(cost: list\[int\]) -\> int:
>
> \"\"\" Минимальная стоимость подъема по лестнице: динамическое программирова- ние.\"\"\"
>
> n = len(cost) - 1
>
> if n == 1 or n == 2: return cost\[n\]
>
> \# Инициализация таблицы dp для хранения решений подзадач. dp = \[0\] \* (n + 1)
>
> \# Начальное состояние: предусмотреть решение минимальной подзадачи. dp\[1\], dp\[2\] = cost\[1\], cost\[2\]
>
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
>
> dp\[i\] = min(dp\[i - 1\], dp\[i - 2\]) + cost\[i\] return dp\[n\]
>
> На рис. 14.7 демонстрируется процесс динамического программирования в данном коде.
>
> ![](ru/docs/assets/media/image852.jpeg)
>
> **Рис. 14.7.** Процесс динамического программирования для задачи минимальной стоимости подъема по лестнице
>
> Эту задачу также можно оптимизировать по пространству, сжав одномерное представление до нулевого, что снижает сложность по пространству с *O*(*n*) до *O*(1).
>
> \# === File: min_cost_climbing_stairs_dp.py ===
>
> def min_cost_climbing_stairs_dp_comp(cost: list\[int\]) -\> int:
>
> \"\"\" Минимальная стоимость подъема по лестнице: динамическое программирова- ние с оптимизацией по пространству.\"\"\"
>
> n = len(cost) - 1
>
> if n == 1 or n == 2: return cost\[n\]
>
> a, b = cost\[1\], cost\[2\] for i in range(3, n + 1):
>
> a, b = b, min(a, b) + cost\[i\] return b

### Отсутствие последствий

> *Отсутствие последствий* -- одно из важных свойств, позволяющих динамиче- скому программированию эффективно решать задачи. Оно определяется сле- дующим образом: **при заданном определенном состоянии его дальней- шее развитие зависит только от текущего состояния и не зависит от всех предыдущих состояний**.
>
> Возьмем, к примеру, задачу о подъеме по лестнице. При заданном состоя- нии *i* оно может развиться в состояния *i* + 1 или *i* + 2, что соответствует подъ- ему на одну или две ступени. При выборе одного из этих вариантов нет не- обходимости учитывать состояния, предшествующие *i*, так как они не влияют на будущее состояние.
>
> Однако, если добавить к задаче о подъеме по лестнице ограничения, ситуа- ция изменится.
>
> Как показано на рис. 14.8, для достижения 3-й ступени остается только два возможных варианта. Вариант с тремя последовательными подъемами по од- ной ступени не удовлетворяет условиям и поэтому отбрасывается.

![](ru/docs/assets/media/image854.jpeg)

> **Рис. 14.8.** Количество вариантов достижения 3-й ступени с учетом ограничений
>
> В этой задаче если на предыдущем шаге был совершен подъем на одну ступень, то на следующем шаге необходимо обязательно подняться на две ступени. Это означает, что **выбор следующего шага нельзя определить независимо от текущего состояния (текущей ступени)**. **Но следующий шаг также зависит и от предыдущего состояния (ступени на предыду- щем шаге)**.
>
> Нетрудно заметить, что данная задача не удовлетворяет условию отсутствия последствий. Уравнение перехода состояния *dp*\[*i*\] = *dp*\[*i* -- 1\] + *dp*\[*i* -- 2\] также не работает, так как *dp*\[*i* -- 1\] представляет собой подъем на одну ступень, вклю- чая варианты, в которых на предыдущем шаге был подъем на одну ступень. Чтобы выполнить условия, нельзя напрямую включать *dp*\[*i* -- 1\] в *dp*\[*i*\].
>
> Для этого необходимо расширить определение состояния: **состояние** \[*i*, *j*\] **обозначает нахождение на** *i*-й **ступени**, **при этом на предыдущем шаге был подъем на** *j* **ступеней**, где *j* ∈ {1, 2}. Это определение состояния уже раз- личает, был ли на предыдущем шаге подъем на одну или две ступени.

- Если на предыдущем шаге был подъем на одну ступень, то на шаг до это- го можно было подняться только на две ступени, т. е. *dp*\[*i*, 1\] можно полу- чить только из *dp*\[*i* -- 1, 2\].

  - Если на предыдущем шаге был подъем на две ступени, то на шаг до этого можно было выбрать подъем на одну или две ступени, т. е. *dp*\[*i*, 2\] можно получить из *dp*\[*i* -- 2, 1\] или *dp*\[*i* -- 2, 2\].

> При таком определении *dp*\[*i*, *j*\] обозначает количество вариантов для состо- яния \[*i*, *j*\], как показано на рис. 14.9. В этом случае уравнение перехода состоя- ния будет следующим:
>
> ρ *dp* ℘Λ*i*, 1λϑ *= dp* ℘Λ*i* −1, 2λϑ
>
>  
>
>  λ*dp* ℘Λ*i*, 2λϑ *= dp* ℘Λ*i* − 2, 1λϑ + *dp* ℘Λ*i* − 2, 2λϑ.

![](ru/docs/assets/media/image856.jpeg)

> **Рис. 14.9.** Рекуррентное соотношение с учетом ограничений
>
> В результате возвращается сумма *dp*\[*n*, 1\] + *dp*\[*n*, 2\], которая представляет общее количество вариантов достижения *n*-й ступени.
>
> \# === File: climbing_stairs_constraint_dp.py === def climbing_stairs_constraint_dp(n: int) -\> int:
>
> \"\"\" Динамическое программирование для подъема по лестнице
>
> с ограничениями.\"\"\"
>
> if n == 1 or n == 2: return 1
>
> \# Инициализация таблицы dp для хранения решений подзадач.
>
> dp = \[\[0\] \* 3 for \_ in range(n + 1)\]
>
> \# Начальное состояние: предустановка решения минимальной подзадачи. dp\[1\]\[1\], dp\[1\]\[2\] = 1, 0
>
> dp\[2\]\[1\], dp\[2\]\[2\] = 0, 1
>
> \# Переход состояния: постепенное решение более крупных подзадач. for i in range(3, n + 1):
>
> dp\[i\]\[1\] = dp\[i - 1\]\[2\]
>
> dp\[i\]\[2\] = dp\[i - 2\]\[1\] + dp\[i - 2\]\[2\] return dp\[n\]\[1\] + dp\[n\]\[2\]
>
> В приведенном выше примере необходимо учитывать только одно преды- дущее состояние, поэтому можно расширить определение состояния, и задача все равно будет удовлетворять условию отсутствия последствий. Однако неко- торые задачи обладают серьезными условиями последствий.
>
> В этой задаче следующий шаг зависит от всех предыдущих состояний, так как каждый предыдущий шаг устанавливает препятствие на более высокой ступени. Для таких задач динамическое программирование часто оказывается неэффективным.
>
> На самом деле многие сложные задачи комбинаторной оптимизации (на- пример, задача коммивояжера) не удовлетворяют условию отсутствия по- следствий. Для решения таких задач обычно выбираются другие методы, та- кие как эвристический поиск, генетические алгоритмы, обучение с подкре- плением и т. д., чтобы получить приемлемое локальное оптимальное решение за ограниченное время.

#### подход к решению задач динамического программирования

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

1.  Как определить, является ли задача задачей динамического программи- рования?

2.  С чего начать решение задачи динамического программирования, како- ва полная схема решения?

### Определение задачи

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

- Задача содержит описание оптимизации, например максимизацию или минимизацию.

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

> Соответственно, существуют маркеры, которые говорят о неприменимости стратегии динамического программирования.

- Цель задачи -- найти все возможные решения, а не оптимальное решение.

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

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

### Этапы решения задачи

> Процесс решения задач динамического программирования может разли- чаться в зависимости от природы и сложности задачи, но обычно следует следующей схеме: описание решений, определение состояния, построение таблицы *dp*, вывод уравнения перехода состояния, определение граничных условий и т. д.
>
> Для более наглядного представления этапов решения рассмотрим в каче- стве примера классическую задачу «минимальная стоимость пути».
>
> На рис. 14.10 показан пример, в котором минимальная сумма пути для дан- ного массива равна 13.
>
> ![](ru/docs/assets/media/image858.jpeg)
>
> **Рис. 14.10.** Пример данных для задачи минимальной стоимости пути

##### Шаг 1: обдумывание каждого решения, определение состояния, получение таблицы *dp*

> В этой задаче решение заключается в выборе следующего шага из текущей ячейки: вниз или вправо. Обозначим текущий индекс строки и столбца как \[*i*, *j*\], тогда после шага вниз или вправо индекс изменится на \[*i* + 1, *j*\] или \[*i*, *j* + 1\]. Таким образом, состояние должно включать два переменных индекса: строки и столбца, обозначаемых как \[*i*, *j*\].
>
> Подзадача, соответствующая состоянию \[*i*, *j*\], заключается в нахождении ми- нимальной стоимости пути от начальной точки \[0, 0\] до точки \[*i*, *j*\], решение обозначается как *dp*\[*i*, *j*\].
>
> Таким образом, мы получаем двумерную матрицу *dp*, размер которой со- впадает с размером входного массива *grid*, как показано на рис. 14.11.
>
> **Решение:** пройти на одну клетку вправо или вниз
>
> **Определение состояния:** индексы строки и столбца **\[i, j\]**
>
> **Таблица dp**
>
> ![](ru/docs/assets/media/image860.jpeg)**Подзадача:** минимальная сумма пути из левого верхнего угла до **\[i, j\]**
>
> **Таблица dp:** матрица того же размера, что и grid
>
> **Рис. 14.11.** Определение состояния и таблица dp

##### Шаг 2: нахождение оптимальной подструктуры и вывод уравнения перехода состояния

> Переход в состояние \[*i*, *j*\] возможен только из верхней ячейки \[*i* − 1, *j*\] или левой ячейки \[*i*, *j* − 1\]. Таким образом, оптимальная подструктура определяется тем, что минимальная сумма пути до \[*i*, *j*\] определяется минимальной суммой пути из \[*i*, *j* − 1\] и \[*i* − 1, *j*\].
>
> На основе вышеизложенного можно вывести уравнение перехода состоя- ния, показанное на рис. 14.12:
>
> *dp* Λ℘*i*, *j* λϑ *=* min(*dp* ℘Λ*i* −1λϑ , *dp* ℘Λ*i, j* −1λϑ + *grid* ℘Λ*i, j*λϑ .

![](ru/docs/assets/media/image862.jpeg)

> **Рис. 14.12.** Оптимальная подструктура и уравнение перехода состояния

##### Шаг 3: определение граничных условий и порядка перехода состояния

> В этой задаче состояния в первой строке можно получить только из левых со- стояний, а состояния в первом столбце -- только из верхних состояний, поэто- му первая строка *i* = 0 и первый столбец *j* = 0 являются граничными условиями. Поскольку каждую ячейку можно получить только из ячейки слева или сверху, мы используем цикл для обхода матрицы: внешний цикл проходит по
>
> строкам, а внутренний -- по столбцам, как показано на рис. 14.13.
>
> ![](ru/docs/assets/media/image864.jpeg)**Граничные условия:** инициализировать первые строку и столбец
>
> **Порядок перехода состояний:**
>
> прямой обход матрицы
>
> **Рис. 14.13.** Граничные условия и порядок перехода состояний
>
> На основе вышеизложенного анализа можно сразу написать код динами- ческого программирования. Однако разбиение подзадач -- это подход сверху вниз, поэтому реализация в порядке полный перебор → мемоизация → дина- мическое программирование более соответствует привычному мышлению.

##### Первый метод: полный перебор

> Поиск начинается с состояния \[*i*, *j*\] и постоянно разбивается на более мелкие со- стояния \[*i* -- 1, *j*\] и \[*i*, *j* -- 1\]. Рекурсивная функция включает следующие элементы.

- **Рекурсивные параметры**: состояние \[*i*, *j*\].

- **Возвращаемое значение**: минимальная стоимость пути от \[0, 0\] до \[*i*, *j*\], *dp*\[*i*, *j*\].

- **Условие завершения**: когда *i* = 0 и *j* = 0, возвращается стоимость *grid*\[0, 0\].

- **Обрезка**: при *i* \< 0 или *j* \< 0 индекс выходит за допустимые пределы, в этом случае возвращается стоимость +∞, что означает недопустимость.

> Ниже приведен код реализации.
>
> \# === File: min_path_sum.py ===
>
> def min_path_sum_dfs(grid: list\[list\[int\]\], i: int, j: int) -\> int: \"\"\" Минимальная стоимость пути: полный перебор.\"\"\"
>
> \# Если это верхний левый элемент, то поиск завершается. if i == 0 and j == 0:
>
> return grid\[0\]\[0\]
>
> \# Если индексы строки и столбца выходят за пределы, возвращается стоимость +∞. if i \< 0 or j \< 0:
>
> return inf
>
> \# Вычисление минимальной стоимости пути от верхнего левого угла до (i-1, j) и (i, j-1).
>
> up = min_path_sum_dfs(grid, i - 1, j) left = min_path_sum_dfs(grid, i, j - 1)
>
> \# Возвращение минимальной стоимости пути от верхнего левого угла до (i, j). return min(left, up) + grid\[i\]\[j\]
>
> На рис. 14.14 изображено дерево рекурсии с корневым узлом *dp*\[2, 1\], содер- жащее несколько перекрывающихся подзадач, количество которых резко уве- личивается с увеличением размера сетки grid.
>
> По сути, причиной перекрывающихся подзадач является **наличие несколь- ких путей**, **ведущих из верхнего левого угла к одной ячейке**.

![](ru/docs/assets/media/image866.jpeg)

> **Рис. 14.14.** Дерево рекурсии полного перебора
>
> Каждое состояние имеет два варианта выбора: вниз и вправо. Чтобы пройти из верхнего левого угла в нижний правый, требуется *m* + *n* -- 2 шагов, поэтому в худшем случае временная сложность составляет *O*(2*m*+*n*). Обратите внимание, что этот расчет не учитывает случаи, когда путь достигает границы сетки, где остается только один вариант выбора, поэтому фактическое количество путей будет меньше.

##### Второй метод: мемоизация

> Вводится список mem, имеющий те же размеры, что и сетка grid, для записи ре- шений подзадач и отсечения перекрывающихся подзадач.
>
> \# === File: min_path_sum.py === def min_path_sum_dfs_mem(
>
> grid: list\[list\[int\]\], mem: list\[list\[int\]\], i: int, j: int
>
> ) -\> int:
>
> \"\"\" Минимальная стоимость пути: мемоизация.\"\"\"
>
> \# Если это верхний левый элемент, то поиск завершается. if i == 0 and j == 0:
>
> return grid\[0\]\[0\]
>
> \# Если индексы строки и столбца выходят за пределы, возвращается стоимость +∞. if i \< 0 or j \< 0:
>
> return inf
>
> \# Если уже есть запись, то возвращается она. if mem\[i\]\[j\] != -1:
>
> return mem\[i\]\[j\]
>
> \# Минимальная стоимость пути от левого и верхнего элементов. up = min_path_sum_dfs_mem(grid, mem, i - 1, j)
>
> left = min_path_sum_dfs_mem(grid, mem, i, j - 1)
>
> \# Запись и возвращение минимальной стоимости пути от верхнего левого \# угла до (i, j).
>
> mem\[i\]\[j\] = min(left, up) + grid\[i\]\[j\] return mem\[i\]\[j\]
>
> После введения мемоизации решения всех подзадач вычисляются только один раз, как показано на рис. 14.15. Поэтому временная сложность зависит от общего числа состояний, т. е. от размера сетки *O*(*nm*).

![](ru/docs/assets/media/image868.jpeg)

> **Рис. 14.15.** Дерево рекурсии мемоизации

##### Третий метод: динамическое программирование

> Ниже представлена реализация решения с использованием итеративного под- хода динамического программирования.
>
> \# === File: min_path_sum.py ===
>
> def min_path_sum_dp(grid: list\[list\[int\]\]) -\> int:
>
> \"\"\" Минимальная стоимость пути: динамическое программирование.\"\"\" n, m = len(grid), len(grid\[0\])
>
> \# Инициализация таблицы dp.
>
> dp = \[\[0\] \* m for \_ in range(n)\] dp\[0\]\[0\] = grid\[0\]\[0\]
>
> \# Переход состояния: первая строка. for j in range(1, m):
>
> dp\[0\]\[j\] = dp\[0\]\[j - 1\] + grid\[0\]\[j\] \# Переход состояния: первый столбец.
>
> for i in range(1, n):
>
> dp\[i\]\[0\] = dp\[i - 1\]\[0\] + grid\[i\]\[0\]
>
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n):
>
> for j in range(1, m):
>
> dp\[i\]\[j\] = min(dp\[i\]\[j - 1\], dp\[i - 1\]\[j\]) + grid\[i\]\[j\] return dp\[n - 1\]\[m - 1\]
>
> На рис. 14.16 демонстрируется процесс перехода состояний для минималь- ной стоимости пути, который охватывает всю сетку, поэтому **временная сложность составляет** *O*(*nm*). Размер массива *dp* равен *n*×*m*, следовательно, **пространственная сложность также составляет** *O*(*nm*).

![](ru/docs/assets/media/image870.jpeg)

> **Рис. 14.16.** Динамическое программирование для минимальной стоимости пути. Шаг 1
>
> ![](ru/docs/assets/media/image873.jpeg)

![](ru/docs/assets/media/image876.jpeg)![](ru/docs/assets/media/image878.jpeg)

> **Рис. 14.16.** *Продолжение*. Шаги 2--4
>
> ![](ru/docs/assets/media/image880.jpeg)

![](ru/docs/assets/media/image882.jpeg)![](ru/docs/assets/media/image884.jpeg)

> **Рис. 14.16.** *Продолжение*. Шаги 5--7
>
> ![](ru/docs/assets/media/image886.jpeg)

![](ru/docs/assets/media/image888.jpeg)![](ru/docs/assets/media/image890.jpeg)

> **Рис. 14.16.** *Продолжение*. Шаги 8--10
>
> ![](ru/docs/assets/media/image892.jpeg)

![](ru/docs/assets/media/image894.jpeg)

> **Рис. 14.16.** *Окончание*. Шаги 11--12

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

> Поскольку каждая ячейка зависит только от ячеек слева и сверху, для реали- зации таблицы *dp* можно использовать одномерный массив. Обратите внима- ние, что, поскольку массив dp может представлять только одну строку состоя- ния, невозможно заранее инициализировать состояние первого столбца, его необходимо обновлять при обходе каждой строки.
>
> \# === File: min_path_sum.py ===
>
> def min_path_sum_dp_comp(grid: list\[list\[int\]\]) -\> int:
>
> \"\"\" Минимальная стоимость пути: динамическое программирование с оптимизацией пространства.\"\"\"
>
> n, m = len(grid), len(grid\[0\]) \# Инициализация таблицы dp.
>
> dp = \[0\] \* m
>
> \# Переход состояния: первая строка. dp\[0\] = grid\[0\]\[0\]
>
> for j in range(1, m):
>
> dp\[j\] = dp\[j - 1\] + grid\[0\]\[j\]
>
> \# Переход состояния: остальные строки. for i in range(1, n):
>
> \# Переход состояния: первый столбец. dp\[0\] = dp\[0\] + grid\[i\]\[0\]
>
> \# Переход состояния: остальные столбцы. for j in range(1, m):
>
> dp\[j\] = min(dp\[j - 1\], dp\[j\]) + grid\[i\]\[j\] return dp\[m - 1\]

#### задача о рюкзаке 0-1

> Задача о рюкзаке является отличным примером для начала изучения динами- ческого программирования и представляет собой одну из наиболее распростра- ненных форм этой задачи. Существует множество ее вариаций, таких как задача о рюкзаке 0-1, задача о полном рюкзаке, задача о многократном рюкзаке и др.
>
> В этом разделе мы сначала решим наиболее распространенную задачу о рюкзаке 0-1.
>
> Обратите внимание на рис. 14.17: поскольку нумерация предметов *i* начи- нается с 1, а индексация массива с 0, то предмету *i* соответствует масса *wgt*\[*i* -- 1\] и стоимость *val*\[*i* -- 1\].

![](ru/docs/assets/media/image897.jpeg)

> **Рис. 14.17.** Пример данных для задачи о рюкзаке 0-1
>
> Задачу о рюкзаке 0-1 можно рассматривать как процесс, состоящий из *n* эта- пов принятия решений. Для каждого предмета существует два решения: не класть в рюкзак или класть. Таким образом, задача соответствует модели дерева решений. Цель задачи -- найти максимальную стоимость предметов, которые можно поместить в рюкзак при заданной вместимости, что с высокой вероятностью
>
> является задачей динамического программирования.

####### Шаг 1: обдумывание каждого этапа принятия решения, определение состояния, получение таблицы dp

> Для каждого предмета справедливо утверждение: если предмет не класть в рюкзак, вместимость рюкзака не изменится; если класть, вместимость умень- шится. Отсюда определяется состояние: текущий номер предмета *i* и вмести- мость рюкзака *c*, обозначается как \[*i*, *c*\].
>
> Подзадача, соответствующая состоянию \[*i*, *c*\], заключается в **нахождении максимальной стоимости первых** *i* **предметов в рюкзаке вместимостью** *c*, обозначается как *dp*\[*i*, *c*\].
>
> Требуется получить *dp*\[*n*, *cap*\], поэтому необходима двумерная таблица dp размером (*n* + 1) × (*cap* + 1).

####### Шаг 2: выявление оптимальной подструктуры и вывод уравнения перехода состояния

> После принятия решения по предмету *i* остается подзадача принятия решений для первых *i* -- 1 предметов, которая делится на следующие два случая:

1)  **не класть предмет** *i*: вместимость рюкзака не изменяется, состояние переходит в \[*i* -- 1, *c*\];

2)  **класть предмет** *i*: вместимость рюкзака уменьшается на *wgt*\[*i* -- 1\], стои- мость увеличивается на *val*\[*i* -- 1\], состояние переходит в \[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\].

> Этот анализ показывает оптимальную подструктуру задачи: **максимальная стоимость** *dp*\[*i*, *c*\] **равна большей из двух стоимостей**: **не класть предмет** *i* **и класть предмет** *i*. Отсюда выводится уравнение перехода состояния:
>
> *dp*\[*i*, *c*\] = max(*dp*\[*i* -- 1, *c*\], *dp*\[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\] + *val*\[*i* -- 1\]).
>
> Следует отметить, что если текущая масса предмета wgt\[*i* -- 1\] превышает оставшуюся вместимость рюкзака c, то можно выбрать только не класть пред- мет в рюкзак.

####### Шаг 3: определение граничных условий и порядка перехода состояния

> Когда нет предметов или вместимость рюкзака равна 0, максимальная стои- мость равна 0, т. е. первый столбец *dp*\[*i*, 0\] и первая строка *dp*\[0, *c*\] равны 0.
>
> Текущее состояние \[*i*, *c*\] исходит из верхнего состояния \[*i* -- 1, *c*\] и левого верх- него состояния \[*i* -- 1, *c* -- *wgt*\[*i* -- 1\]\], поэтому достаточно пройтись по всей табли- це *dp* двумя вложенными циклами.
>
> На основе вышеизложенного анализа реализуем методы полного перебора, мемоизации поиска и динамического программирования.

1.  **Первый метод: полный перебор**

> Код поиска включает следующие элементы.

- **Рекурсивные параметры**: состояние \[*i*, *c*\].

- **Возвращаемое значение**: решение подзадачи *dp*\[*i*, *c*\].

<!-- -->

- **Условие завершения**: номер предмета выходит за пределы *i* = 0 или оставшаяся вместимость рюкзака равна 0, рекурсия завершается и воз- вращается стоимость 0.

- **Обрезка**: если текущая масса предмета превышает оставшуюся вмести- мость рюкзака, можно выбрать только не класть предмет в рюкзак.

> \# === File: knapsack.py ===
>
> def knapsack_dfs(wgt: list\[int\], val: list\[int\], i: int, c: int) -\> int: \"\"\" Рюкзак 0-1: полный перебор.\"\"\"
>
> \# Если все предметы выбраны или рюкзак не имеет оставшейся вместимости, \# возвращается стоимость 0.
>
> if i == 0 or c == 0: return 0
>
> \# Если вес превышает вместимость рюкзака, можно выбрать только не класть \# в рюкзак.
>
> if wgt\[i - 1\] \> c:
>
> return knapsack_dfs(wgt, val, i - 1, c)
>
> \# Вычисление максимальной стоимости без предмета i и с ним. no = knapsack_dfs(wgt, val, i - 1, c)
>
> yes = knapsack_dfs(wgt, val, i - 1, c - wgt\[i - 1\]) + val\[i - 1\] \# Возвращение большей из двух стоимостей.
>
> return max(no, yes)
>
> Поскольку каждый предмет создает две ветви поиска -- не выбирать и выби- рать, временная сложность составляет *O*(2*n*), как показано на рис. 14.18.
>
> ![](ru/docs/assets/media/image900.jpeg)При наблюдении за деревом рекурсии легко заметить наличие перекрыва- ющихся подзадач, таких как *dp*\[1, 10\]. А когда количество предметов и вмести- мость рюкзака велики, особенно если есть много предметов с одинаковым ве- сом, количество перекрывающихся подзадач значительно увеличивается.

+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+
| *Нет*     |        |              |     | > *Да* |     | > *Положить предмет 3?*                                |
+===========+========+==============+=====+========+=====+========================================================+
|           |        |              |     |        |     | > **Обрезка:** *Масса предмета \> Вместимость рюкзака* |
+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+
| > *Нет*   | > *Да* | *Не*         | *т* |        |     | > *Да Положить предмет* **2***?*                       |
+-----------+--------+--------------+-----+--------+-----+--------------------------------------------------------+

> **Рис. 14.18.** Дерево рекурсии полного перебора для задачи о рюкзаке 0-1

##### Второй метод: мемоизация

> Чтобы вычислять перекрывающиеся подзадачи только один раз, используем список запоминания mem для записи решений подзадач, в котором mem\[i\]\[c\] соответствует *dp*\[*i*, *c*\].
>
> После введения мемоизации временная сложность будет зависеть от коли- чества подзадач, т. е. *O*(*n* × *cap*). Ниже приведен код реализации.
>
> \# === File: knapsack.py === def knapsack_dfs_mem(
>
> wgt: list\[int\], val: list\[int\], mem: list\[list\[int\]\], i: int, c: int
>
> ) -\> int:
>
> \"\"\" Рюкзак 0-1: мемоизация\"\"\"
>
> \# Если все предметы выбраны или в рюкзаке нет оставшейся вместимости, \# возвращается значение 0.
>
> if i == 0 or c == 0: return 0
>
> \# Если запись уже существует, возврат напрямую. if mem\[i\]\[c\] != -1:
>
> return mem\[i\]\[c\]
>
> \# Если превышает вместимость рюкзака, выбирается не класть в рюкзак. if wgt\[i - 1\] \> c:
>
> return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
>
> \# Вычисление максимальной стоимости без и с включением предмета i. no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
>
> yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt\[i - 1\]) + val\[i - 1\] \# Запись и возврат наибольшей стоимости из двух вариантов.
>
> mem\[i\]\[c\] = max(no, yes) return mem\[i\]\[c\]
>
> На рис. 14.19 изображены обрезанные ветви поиска в процессе мемоизации.

![](ru/docs/assets/media/image902.jpeg)

> **Рис. 14.19.** Рекурсивное дерево мемоизации для задачи о рюкзаке 0-1

##### Третий метод: динамическое программирование

> Динамическое программирование представляет собой процесс заполнения таблицы *dp* в процессе перехода между состояниями, как показано в коде ниже.
>
> \# === File: knapsack.py ===
>
> def knapsack_dp(wgt: list\[int\], val: list\[int\], cap: int) -\> int: \"\"\" Рюкзак 0-1: динамическое программирование.\"\"\"
>
> n = len(wgt)
>
> \# Инициализация таблицы dp.
>
> dp = \[\[0\] \* (cap + 1) for \_ in range(n + 1)\] \# Переход между состояниями.
>
> for i in range(1, n + 1):
>
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
>
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[i\]\[c\] = dp\[i - 1\]\[c\]
>
> else:
>
> \# Наибольшее значение из двух вариантов: не выбирать \# и выбирать предмет i.
>
> dp\[i\]\[c\] = max(dp\[i - 1\]\[c\], dp\[i - 1\]\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[n\]\[cap\]
>
> Временная и пространственная сложность определяются размером массива
>
> *dp*, т. е. *O*(*n* × *cap*), как показано на рис. 14.20.

![](ru/docs/assets/media/image904.jpeg)

> **Рис. 14.20.** Динамическое программирование для задачи о рюкзаке 0-1. Шаг 1
>
> ![](ru/docs/assets/media/image906.jpeg)

![](ru/docs/assets/media/image908.jpeg)![](ru/docs/assets/media/image910.jpeg)

> **Рис. 14.20.** *Продолжение*. Шаги 2--4
>
> ![](ru/docs/assets/media/image912.jpeg)

![](ru/docs/assets/media/image914.jpeg)![](ru/docs/assets/media/image916.jpeg)

> **Рис. 14.20.** *Продолжение*. Шаги 5--7
>
> ![](ru/docs/assets/media/image918.jpeg)

![](ru/docs/assets/media/image920.jpeg)![](ru/docs/assets/media/image922.jpeg)

> **Рис. 14.20.** *Продолжение*. Шаги 8--10
>
> ![](ru/docs/assets/media/image924.jpeg)

![](ru/docs/assets/media/image926.jpeg)![](ru/docs/assets/media/image928.jpeg)

> **Рис. 14.20.** *Продолжение*. Шаги 11--13
>
> ![](ru/docs/assets/media/image930.jpeg)
>
> **Рис. 14.20.** *Окончание*. Шаг 14

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

> Поскольку каждое состояние зависит только от состояния предыдущей строки, можно использовать два массива для продвижения и снизить пространствен- ную сложность с *O*(*n*2) до *O*(*n*).
>
> А можно ли реализовать оптимизацию пространства, используя только один массив? Заметим, что каждое состояние переходит из верхней или левой верх- ней ячейки. Если используется только один массив, то при начале обхода стро- ки *i* массив все еще хранит состояние строки *i* -- 1.

- Если обход выполняется в прямом порядке, то при достижении *dp*\[*i*, *j*\] значения из левой верхней части *dp*\[*i* -- 1, 1\] \~ *dp*\[*i* -- 1, *j* -- 1\] могут быть уже перезаписаны, что делает невозможным получение правильного резуль- тата перехода состояния.

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

> На рис. 14.21 демонстрируется процесс перехода от строки *i* = 1 к строке *i* = 2 с использованием одного массива. Проанализируйте различия при прямом и обратном обходах.

![](ru/docs/assets/media/image932.jpeg)

> **Рис. 14.21.** Динамическое программирование с оптимизацией пространства для задачи о рюкзаке 0-1. Шаг 1
>
> ![](ru/docs/assets/media/image934.jpeg)

![](ru/docs/assets/media/image936.jpeg)![](ru/docs/assets/media/image938.jpeg)

> **Рис. 14.21.** *Продолжение*. Шаги 2--4
>
> ![](ru/docs/assets/media/image940.jpeg)

+---------------------------------------------------------------------------------------------------------------+
| > Шаг 6 Масса Стоимость                                                                                       |
| >                                                                                                             |
| > **wgt val**                                                                                                 |
| >                                                                                                             |
| > Используется один                                                                                           |
| >                                                                                                             |
| > одномерный массив **dp**                                                                                    |
| >                                                                                                             |
| > После завершения обхода в массиве **dp** содержатся все решения для i = 2                                   |
+=======================================================+===========================+===========================+
|                                                       |                           |                           |
+-------------------------------------------------------+---------------------------+---------------------------+

> ![](ru/docs/assets/media/image942.jpeg)**Рис. 14.21.** *Окончание*. Шаги 5--6
>
> В коде реализации необходимо просто удалить первую размерность *i* из массива dp и изменить внутренний цикл на обратный обход.
>
> \# === File: knapsack.py ===
>
> def knapsack_dp_comp(wgt: list\[int\], val: list\[int\], cap: int) -\> int:
>
> \"\"\" Рюкзак 0-1: динамическое программирование с оптимизацией пространства.\"\"\" n = len(wgt)
>
> \# Инициализация таблицы dp. dp = \[0\] \* (cap + 1)
>
> \# Переход между состояниями. for i in range(1, n + 1):
>
> \# Обратный обход.
>
> for c in range(cap, 0, -1): if wgt\[i - 1\] \> c:
>
> \# Если превышается вместимость рюкзака, то предмет i не выбирается.
>
> dp\[c\] = dp\[c\]
>
> else:
>
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
>
> dp\[c\] = max(dp\[c\], dp\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[cap\]

#### задача о полном рюкзаке

> В этом разделе мы сначала решим еще одну распространенную задачу о рюк- заке -- задачу о полном рюкзаке. А затем рассмотрим ее частный случай -- за- дачу о размене монет.

### Задача о полном рюкзаке

![](ru/docs/assets/media/image946.png)

> **Рис. 14.22.** Пример данных для задачи о полном рюкзаке

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

> Задача о полном рюкзаке очень похожа на задачу о рюкзаке 0-1. **Различие лишь в том**, **что количество выборов предметов не ограничено**.

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

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

> В условиях задачи о полном рюкзаке изменение состояния \[*i*, *c*\] делится на два случая.

- **Не помещать предмет** *i*: аналогично задаче о рюкзаке 0-1, переход к \[*i* -- 1, *[c]{.underline}*\].

- **Помещать предмет** *i*: в отличие от задачи о рюкзаке 0-1, переход к \[*i*, *c* -- *wgt*\[*i* -- 1\]\].

> Таким образом, уравнение перехода состояния меняется на следующее:
>
> *dp*\[*i*, *c*\] = max(*dp*\[*i* -- 1, *c*\], *dp*\[*i*, *c* -- *wgt*\[*i* -- 1\]\] + *val*\[*i* -- 1\]).

##### Код реализации

> По сравнению с кодом предыдущей задачи есть одно изменение в переходе состояния с *i* -- 1 на *i*, остальной код полностью совпадает.
>
> \# === File: unbounded_knapsack.py ===
>
> def unbounded_knapsack_dp(wgt: list\[int\], val: list\[int\], cap: int) -\> int: \"\"\"Полный рюкзак: динамическое программирование.\"\"\"
>
> n = len(wgt)
>
> \# Инициализация таблицы dp.
>
> dp = \[\[0\] \* (cap + 1) for \_ in range(n + 1)\] \# Переход между состояниями.
>
> for i in range(1, n + 1):
>
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
>
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[i\]\[c\] = dp\[i - 1\]\[c\]
>
> else:
>
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
>
> dp\[i\]\[c\] = max(dp\[i - 1\]\[c\], dp\[i\]\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[n\]\[cap\]

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

> Поскольку текущее состояние исходит из состояний слева и сверху, **после оп- тимизации пространства следует выполнять прямой обход каждой стро- ки в таблице** *dp*.
>
> Этот порядок обхода противоположен порядку в задаче о рюкзаке 0-1. Из- учите рис. 14.23 для понимания различий между ними.
>
> ![](ru/docs/assets/media/image950.jpeg)

![](ru/docs/assets/media/image952.jpeg)![](ru/docs/assets/media/image954.jpeg)

> **Рис. 14.23.** Динамическое программирование для задачи о полном рюкзаке после оптими- зации пространства. Шаги 1--3

![](ru/docs/assets/media/image956.jpeg)![](ru/docs/assets/media/image958.jpeg)

+---------------------------------------------------------------------------------------------+
| > Шаг 4 Масса Стоимость                                                                     |
| >                                                                                           |
| > **wgt val**                                                                               |
| >                                                                                           |
| > Используется один                                                                         |
| >                                                                                           |
| > одномерный массив **dp**                                                                  |
| >                                                                                           |
| > Прямой обход строки i = 2, выполнение перехода состояния                                  |
+========================+===========================================+========================+
|                        |                                           |                        |
+------------------------+-------------------------------------------+------------------------+

+---------------------------------------------------------------------------------------------+
| > Шаг 5 Масса Стоимость                                                                     |
| >                                                                                           |
| > **wgt val**                                                                               |
| >                                                                                           |
| > Используется один                                                                         |
| >                                                                                           |
| > одномерный массив **dp**                                                                  |
| >                                                                                           |
| > Прямой обход строки i = 2, выполнение перехода состояния                                  |
+========================+===========================================+========================+
|                        |                                           |                        |
+------------------------+-------------------------------------------+------------------------+

![](ru/docs/assets/media/image960.jpeg)

> **Рис. 14.23.** *Окончание*. Шаги 4--6
>
> Код реализации достаточно прост, необходимо лишь удалить первую раз- мерность массива dp.
>
> \# === File: unbounded_knapsack.py ===
>
> def unbounded_knapsack_dp_comp(wgt: list\[int\], val: list\[int\], cap: int) -\>
>
> int:
>
> \"\"\" Полный рюкзак: динамическое программирование с оптимизацией пространства.\"\"\" n = len(wgt)
>
> \# Инициализация таблицы dp. dp = \[0\] \* (cap + 1)
>
> \# Переход состояния.
>
> for i in range(1, n + 1): \# Прямой обход.
>
> for c in range(1, cap + 1): if wgt\[i - 1\] \> c:
>
> \# Если превышается вместимость рюкзака, то предмет i не выбирается. dp\[c\] = dp\[c\]
>
> else:
>
> \# Наибольшее значение из двух вариантов: не выбирать и выбирать \# предмет i.
>
> dp\[c\] = max(dp\[c\], dp\[c - wgt\[i - 1\]\] + val\[i - 1\]) return dp\[cap\]

### Задача о размене монет

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

![](ru/docs/assets/media/image962.jpeg)

> **Рис. 14.24.** Пример данных для задачи о размене монет

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

> **Задачу о размене монет можно рассматривать как частный случай зада- чи о полном рюкзаке** со следующими сходствами и различиями.

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

- Цели оптимизации противоположны: задача о полном рюкзаке стре- мится максимизировать стоимость предметов, задача о размене монет -- минимизировать количество монет.

- Задача о полном рюкзаке ищет решение, не превышающее вместимость рюкзака, задача о размене монет -- решение, точно соответствующее це- левой сумме.

####### Шаг 1: определение каждого этапа принятия решения, определение состояния для получения таблицы dp

> Подзадача состояния \[*i*, *a*\] заключается в **нахождении минимального коли- чества монет для составления суммы** *a* **из первых** *i* **видов монет**, обозна- чается как *dp*\[*i*, *a*\].
>
> Размер двумерной таблицы *dp* равен (*n* + 1) × (*amt* + 1).

####### Шаг 2: нахождение оптимальной подструктуры и выведение уравнения перехода состояния

> В этой задаче уравнение перехода состояния отличается от задачи о полном рюкзаке в двух моментах.

- В этой задаче требуется найти минимальное значение, поэтому опера- тор max() заменяется на min().

- Оптимизация направлена на количество монет, а не на стоимость това- ров, поэтому при выборе монеты выполняется операция +1.

> *dp*\[*i*, *a*\] = min(*dp*\[*i* -- 1, *a*\], *dp*\[*i*, *a* -- *coins*\[*i* -- 1\]\] + 1).

####### Шаг 3: определение граничных условий и порядка перехода состояния

> Когда целевая сумма равна 0, минимальное количество монет для ее составле- ния равно 0, т. е. все *dp*\[*i*, 0\] в первом столбце равны 0.
>
> При отсутствии монет **невозможно составить любую целевую сумму** \> 0, это является недопустимым решением. Чтобы функция min() в уравнении пе- рехода состояния могла распознавать и фильтровать недопустимые решения, предлагается использовать значение +∞ для их обозначения, т. е. все *dp*\[0, *a*\] в первой строке равны +∞.

##### Код реализации

> В большинстве языков программирования нет представления для значения +∞, поэтому часто используется максимальное значение типа int. Однако это может привести к переполнению при выполнении операции +1 в уравнении перехода. Поэтому для обозначения недопустимого решения будем использовать чис- ло *amt* + 1, поскольку максимальное количество монет для составления *amt* равно *amt*. Перед возвратом проверяется, равно ли *dp*\[*n*, *amt*\] значению *amt* + 1.
>
> Если равно, возвращается --1, что означает невозможность составления целе- вой суммы. Ниже приведен код реализации.
>
> \# === File: coin_change.py ===
>
> def coin_change_dp(coins: list\[int\], amt: int) -\> int: \"\"\" Размен монет: динамическое программирование.\"\"\" n = len(coins)
>
> MAX = amt + 1
>
> \# Инициализация таблицы dp.
>
> dp = \[\[0\] \* (amt + 1) for \_ in range(n + 1)\]
>
> \# Переход состояния: первая строка и первый столбец. for a in range(1, amt + 1):
>
> dp\[0\]\[a\] = MAX
>
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n + 1):
>
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
>
> \# Если превышается целевая сумма, то монета i не выбирается. dp\[i\]\[a\] = dp\[i - 1\]\[a\]
>
> else:
>
> \# Наименьшее значение между не выбирать и выбирать монету i. dp\[i\]\[a\] = min(dp\[i - 1\]\[a\], dp\[i\]\[a - coins\[i - 1\]\] + 1)
>
> return dp\[n\]\[amt\] if dp\[n\]\[amt\] != MAX else -1
>
> На рис. 14.25 демонстрируется процесс динамического программирова- ния для задачи о размене монет, который очень похож на задачу о полном рюкзаке.

![](ru/docs/assets/media/image964.jpeg)

> **Рис. 14.25.** Динамическое программирование задачи о размене монет. Шаг 1

![](ru/docs/assets/media/image965.jpeg){width="3.3324004811898513in" height="1.8960411198600176in"}

> ![](ru/docs/assets/media/image967.jpeg)

![](ru/docs/assets/media/image969.jpeg)

> **Рис. 14.25.** *Продолжение*. Шаги 2--4
>
> ![](ru/docs/assets/media/image971.jpeg)

![](ru/docs/assets/media/image973.jpeg)![](ru/docs/assets/media/image975.jpeg)

> **Рис. 14.25.** *Продолжение*. Шаги 5--7
>
> ![](ru/docs/assets/media/image977.jpeg)

![](ru/docs/assets/media/image979.jpeg)![](ru/docs/assets/media/image981.jpeg)

> **Рис. 14.25.** *Продолжение*. Шаги 8--10
>
> ![](ru/docs/assets/media/image983.jpeg)

![](ru/docs/assets/media/image985.jpeg)![](ru/docs/assets/media/image987.jpeg)

> **Рис. 14.25.** *Продолжение*. Шаги 11--13
>
> ![](ru/docs/assets/media/image989.jpeg)

![](ru/docs/assets/media/image991.jpeg)

> **Рис. 14.25.** *Окончание*. Шаги 14--15

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

> Оптимизация пространства в задаче о размене монет осуществляется анало- гично задаче о полном рюкзаке.
>
> \# === File: coin_change.py ===
>
> def coin_change_dp_comp(coins: list\[int\], amt: int) -\> int:
>
> \"\"\" Размен монет: динамическое программирование с оптимизацией простран- ства.\"\"\"
>
> n = len(coins)
>
> MAX = amt + 1
>
> \# Инициализация таблицы dp. dp = \[MAX\] \* (amt + 1) dp\[0\] = 0
>
> \# Переход состояния.
>
> for i in range(1, n + 1): \# Прямой обход.
>
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
>
> \# Если превышается целевая сумма, то не выбирается монета i. dp\[a\] = dp\[a\]
>
> else:
>
> \# Наименьшее значение между не выбирать и выбирать монету i. dp\[a\] = min(dp\[a\], dp\[a - coins\[i - 1\]\] + 1)
>
> return dp\[amt\] if dp\[amt\] != MAX else -1

### 14.5.3 Задача о размене монет II

![](ru/docs/assets/media/image993.jpeg)

> **Рис. 14.26.** Пример данных для задачи о размене монет II

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

> В отличие от предыдущей задачи здесь целью является определение количе- ства комбинаций, поэтому подзадача формулируется следующим образом: **количество комбинаций, которыми можно составить сумму** *a*, **используя первые** *i* **видов монет**. Таблица *dp* по-прежнему представляет собой двумер- ную матрицу размером (*n* + 1) × (*amt* + 1).
>
> Количество комбинаций для текущего состояния равно сумме количества комбинаций без выбора текущей монеты и с выбором текущей монеты. Урав- нение перехода состояния имеет вид:
>
> *dp*\[*i*, *a*\] = *dp*\[*i* -- 1, *a*\] + *dp*\[*i*, *a* -- *coins*\[*i* -- 1\]\].
>
> Если целевая сумма равна 0, то для достижения этой суммы не требуется вы- бирать монеты, поэтому все *dp*\[*i*, 0\] в первом столбце нужно инициализировать значением 1. Если монет нет, невозможно составить любую сумму больше 0, поэтому все *dp*\[0, *a*\] в первой строке равны 0.

##### Код реализации

> \# === File: coin_change_ii.py ===
>
> def coin_change_ii_dp(coins: list\[int\], amt: int) -\> int:
>
> \"\"\" Задача о размене монет II: динамическое программирование.\"\"\" n = len(coins)
>
> \# Инициализация таблицы dp.
>
> dp = \[\[0\] \* (amt + 1) for \_ in range(n + 1)\] \# Инициализация первого столбца.
>
> for i in range(n + 1): dp\[i\]\[0\] = 1
>
> \# Переход состояния.
>
> for i in range(1, n + 1):
>
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
>
> \# Если превышается целевая сумма, монета i не выбирается. dp\[i\]\[a\] = dp\[i - 1\]\[a\]
>
> else:
>
> \# Сумма двух вариантов: без выбора и с выбором монеты i. dp\[i\]\[a\] = dp\[i - 1\]\[a\] + dp\[i\]\[a - coins\[i - 1\]\]
>
> return dp\[n\]\[amt\]

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

> Метод оптимизации пространства аналогичен предыдущей задаче, достаточ- но удалить измерение монет.
>
> \# === File: coin_change_ii.py ===
>
> def coin_change_ii_dp_comp(coins: list\[int\], amt: int) -\> int:
>
> \"\"\" Задача о размене монет II: динамическое программирование с оптимизацией пространства.\"\"\"
>
> n = len(coins)
>
> \# Инициализация таблицы dp. dp = \[0\] \* (amt + 1)
>
> dp\[0\] = 1
>
> \# Переход состояния.
>
> for i in range(1, n + 1): \# Прямой обход.
>
> for a in range(1, amt + 1): if coins\[i - 1\] \> a:
>
> \# Если превышает целевую сумму, монета i не выбирается. dp\[a\] = dp\[a\]
>
> else:
>
> \# Сумма двух вариантов: без выбора и с выбором монеты i. dp\[a\] = dp\[a\] + dp\[a - coins\[i - 1\]\]
>
> return dp\[amt\]

#### задача расстояния редактирования

> Расстояние редактирования, также известное как расстояние Левенштейна, -- это минимальное количество изменений, необходимых для преобразования од- ной строки в другую. Обычно используется для измерения сходства двух после- довательностей в информационном поиске и обработке естественного языка.
>
> Для преобразования kitten в sitting требуется три шага редактирования, включая две операции замены и одну операцию добавления, как показано на рис. 14.27. Для преобразования hello в algo требуется три шага, включая две операции замены и одну операцию удаления.

![](ru/docs/assets/media/image995.jpeg)

> **Рис. 14.27.** Пример данных для задачи расстояния редактирования
>
> **Задачу расстояния редактирования можно естественным образом объяснить с помощью модели дерева решений**. Строки соответствуют уз- лам дерева, а один шаг редактирования (одна операция редактирования) соот- ветствует ребру дерева.
>
> При отсутствии ограничений на операции каждый узел может порождать множество ребер, каждое из которых соответствует одной операции, как пока- зано на рис. 14.28. Это означает, что существует множество возможных путей для преобразования hello в algo.
>
> С точки зрения дерева решений цель задачи -- найти кратчайший путь меж- ду узлом hello и узлом algo.

![](ru/docs/assets/media/image997.jpeg)

> **Рис. 14.28.** Представление задачи расстояния редакти- рования на основе модели дерева решений

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

####### Шаг 1: обдумывание каждого этапа решения, определение состояния для получения таблицы dp

> Каждый шаг решения -- это выполнение одной операции редактирования над строкой *s*.
>
> Мы стремимся к тому, чтобы в процессе выполнения операций редактиро- вания размер задачи постепенно уменьшался, что позволяет построить подза- дачи. Пусть длины строк *s* и *t* равны *n* и *m* соответственно. Рассмотрим сначала последние символы этих двух строк *s*\[*n* -- 1\] и *t*\[*m* -- 1\].

- Если *s*\[*n* -- 1\] и *t*\[*m* -- 1\] одинаковы, их можно пропустить и сразу рассмо- треть *s*\[*n* -- 2\] и *t*\[*m* -- 2\].

- Если *s*\[*n* -- 1\] и *t*\[*m* -- 1\] различны, необходимо выполнить одну операцию редактирования над *s* (вставка, удаление, замена), чтобы последние сим- волы двух строк стали одинаковыми. После этого их можно будет про- пустить и рассмотреть задачу меньшего размера.

> Таким образом, каждый шаг решения (операция редактирования) в строке *s* приводит к изменению оставшихся символов, которые необходимо сопоста- вить в *s* и *t*. Поэтому состояние определяется как текущие рассматриваемые *i*-й и *j*-й символы в *s* и *t*, обозначим его как \[*i*, *j*\].
>
> Подзадача, соответствующая состоянию \[*i*, *j*\]: **минимальное количество шагов редактирования**, **необходимых для преобразования первых** *i* **сим- волов** *s* **в первые** *j* **символов** *t*.
>
> Таким образом, получаем двумерную таблицу *dp* размером (*i* + 1) × (*j* + 1).

####### Шаг 2: нахождение оптимальной подструктуры и вывод уравнения перехода состояния

> Рассмотрим подзадачу *dp*\[*i*, *j*\], в которой последние символы двух соответству- ющих строк -- это *s*\[*i* -- 1\] и *t*\[*j* -- 1\]. В зависимости от различных операций редак- тирования можно выделить три случая, представленные на рис. 14.29.

1.  Добавление *t*\[*j* -- 1\] после *s*\[*i* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i*, *j* -- 1\].

2.  Удаление *s*\[*i* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i* -- 1, *j*\].

3.  Замена *s*\[*i* -- 1\] на *t*\[*j* -- 1\], тогда оставшаяся подзадача -- *dp*\[*i* -- 1, *j* -- 1\].

![](ru/docs/assets/media/image999.jpeg)

> **Рис. 14.29.** Переходы состояний для расстояния редактирования
>
> На основании вышеизложенного анализа можно получить оптимальную подструктуру: минимальное количество шагов редактирования для *dp*\[*i*, *j*\] равно минимальному количеству шагов редактирования среди *dp*\[*i*, *j* -- 1\], *dp*\[*i* -- 1, *j*\], *dp*\[*i* -- 1, *j* -- 1\] плюс 1 шаг за текущее редактирование. Соответствую- щее уравнение перехода состояния выглядит следующим образом:
>
> *dp*\[*i*, *j*\] = min(*dp*\[*i*, *j --* 1\], *dp*\[*i* -- 1, *j*\], *dp*\[*i* -- 1, *j --* 1\]) + 1.
>
> Обратите внимание, что **если** *s*\[*i* -- 1\] **и** *t*\[*j* -- 1\] **совпадают**, **то редактирова- ние текущего символа не требуется**, и уравнение перехода состояния в этом случае будет следующим:
>
> *dp*\[*i*, *j*\] = *dp*\[*i* -- 1, *j --* 1\].

####### Шаг 3: определение граничных условий и порядка перехода состояний

> Когда обе строки пусты, количество шагов редактирования равно 0, т. е. *dp*\[0, 0\] = 0. Если *s* пустая, а *t* непустая, минимальное количество шагов редактирования равно длине *t*, т. е. первая строка *dp*\[0, *j*\] = *j*. Если *s* непустая, а *t* пустая, минимальное количество шагов редактирования равно длине *s*, т. е. первый столбец *dp*\[*i*, 0\] = *i*.
>
> Анализируя уравнение перехода состояния, решение *dp*\[*i*, *j*\] зависит от ре- шения слева, сверху и слева сверху. Поэтому можно обойти всю таблицу *dp* в прямом порядке с помощью двух вложенных циклов.

##### Код реализации

> \# === File: edit_distance.py ===
>
> def edit_distance_dp(s: str, t: str) -\> int:
>
> \"\"\" Расстояние редактирования: динамическое программирование.\"\"\" n, m = len(s), len(t)
>
> dp = \[\[0\] \* (m + 1) for \_ in range(n + 1)\]
>
> \# Переход состояния: первая строка и первый столбец. for i in range(1, n + 1):
>
> dp\[i\]\[0\] = i
>
> for j in range(1, m + 1): dp\[0\]\[j\] = j
>
> \# Переход состояния: остальные строки и столбцы. for i in range(1, n + 1):
>
> for j in range(1, m + 1):
>
> if s\[i - 1\] == t\[j - 1\]:
>
> \# Если два символа равны, то они пропускаются. dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\]
>
> else:
>
> \# Минимальное количество шагов редактирования =
>
> \# минимальное количество шагов для вставки, удаления, замены + 1. dp\[i\]\[j\] = min(dp\[i\]\[j - 1\], dp\[i - 1\]\[j\], dp\[i - 1\]\[j - 1\]) + 1
>
> return dp\[n\]\[m\]
>
> Как видно из рис. 14.30, процесс перехода состояния для задачи расстояния редактирования очень похож на задачу о рюкзаке, и его можно рассматривать как заполнение двумерной сетки.

![](ru/docs/assets/media/image1001.jpeg)

> **Рис. 14.30.** Динамическое программирование для расстояния редактирования. Шаг 1

![](ru/docs/assets/media/image1002.jpeg){width="3.4433311461067366in" height="2.0345833333333334in"}

> ![](ru/docs/assets/media/image1004.jpeg)

![](ru/docs/assets/media/image1006.jpeg)

> **Рис. 14.30.** *Продолжение*. Шаги 2--4

![](ru/docs/assets/media/image1007.jpeg){width="3.4471598862642168in" height="2.0345833333333334in"}

![](ru/docs/assets/media/image1009.jpeg)![](ru/docs/assets/media/image1011.jpeg)

> **Рис. 14.30.** *Продолжение*. Шаги 5--7
>
> ![](ru/docs/assets/media/image1013.jpeg)

![](ru/docs/assets/media/image1015.jpeg)![](ru/docs/assets/media/image1017.jpeg)

> **Рис. 14.30.** *Продолжение*. Шаги 8--10
>
> ![](ru/docs/assets/media/image1019.jpeg)

![](ru/docs/assets/media/image1021.jpeg)![](ru/docs/assets/media/image1023.jpeg)

> **Рис. 14.30.** *Продолжение*. Шаги 11--13
>
> ![](ru/docs/assets/media/image1025.jpeg)

![](ru/docs/assets/media/image1027.jpeg)

> **Рис. 14.30.** *Окончание*. Шаги 14--15

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

> Поскольку *dp*\[*i*, *j*\] зависит от *dp*\[*i* -- 1, *j*\], *dp*\[*i*, *j* -- 1\], *dp*\[*i* -- 1, *j* -- 1\], прямой обход те- ряет *dp*\[*i* -- 1, *j* -- 1\], а обратный обход не позволяет заранее построить *dp*\[*i*, *j* -- 1\]. Оба порядка обхода неприемлемы.
>
> Для оптимизации можно использовать переменную leftup, в которой будет временно хранится решение *dp*\[*i* -- 1, *j* -- 1\], что позволит учитывать только ре- шения слева и сверху. В этом случае ситуация аналогична задаче о полном рюк- заке, и можно использовать прямой обход. Код реализации представлен ниже.
>
> \# === File: edit_distance.py ===
>
> def edit_distance_dp_comp(s: str, t: str) -\> int:
>
> \"\"\" Расстояние редактирования: динамическое программирование с оптимизацией пространства.\"\"\"
>
> n, m = len(s), len(t) dp = \[0\] \* (m + 1)
>
> \# Переход состояния: первая строка. for j in range(1, m + 1):
>
> dp\[j\] = j
>
> \# Переход состояния: остальные строки. for i in range(1, n + 1):
>
> \# Переход состояния: первый столбец.
>
> leftup = dp\[0\] \# Временное хранение dp\[i-1, j-1\]. dp\[0\] += 1
>
> \# Переход состояния: остальные столбцы. for j in range(1, m + 1):
>
> temp = dp\[j\]
>
> if s\[i - 1\] == t\[j - 1\]:
>
> \# Если два символа равны, то они пропускаются. dp\[j\] = leftup
>
> else:
>
> \# Минимальное количество шагов редактирования = минимальное \# количество шагов для вставки, удаления, замены + 1.
>
> dp\[j\] = min(dp\[j - 1\], dp\[j\], leftup) + 1
>
> leftup = temp \# Обновление для следующего шага dp\[i-1, j-1\]. return dp\[m\]

#### резюме

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

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

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

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

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

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

<!-- -->

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

##### Задача о рюкзаке

- Задача о рюкзаке -- одна из самых типичных задач динамического про- граммирования, имеющая такие варианты, как рюкзак 0-1, полный рюк- зак и многократный рюкзак.

- Состояние задачи о рюкзаке 0-1 определяется как максимальная сто- имость первых *i* предметов в рюкзаке вместимостью *c*. На основе двух решений -- не класть в рюкзак и класть в рюкзак -- можно получить оп- тимальную подструктуру и построить уравнение перехода состояния. В оптимизации пространства, поскольку каждое состояние зависит от состояний «прямо сверху» и «слева сверху», необходимо обходить список в обратном порядке, чтобы избежать перезаписи состояния слева сверху.

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

> «прямо сверху» и «прямо слева», в оптимизации пространства следует делать обход в прямом порядке.

- Задача о размене монет является вариантом задачи о полном рюкзаке. Она изменяет поиск максимальной стоимости на поиск минимального количества монет. Поэтому в уравнении перехода состояния max() сле- дует заменить на min(). От условия не превышать вместимость рюкзака переходят к условию точно достичь целевой суммы. Для обозначения недопустимого решения, когда невозможно достичь целевой суммы, ис- пользуется значение *amt* + 1.

- В задаче о размене монет II вместо поиска минимального количества монет ищется количество комбинаций монет. Уравнение перехода со- стояния соответственно изменяется с min() на оператор суммы.

##### Задача расстоянии редактирования

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

- Состояние задачи о расстоянии редактирования определяется как минимальное количество шагов редактирования, необходимых для изменения первых *i* символов строки *s* в первые *j* символов строки *t*. Когда *s*\[*i*\] ≠ *t*\[*j*\], существуют три решения: добавление, удаление и за- мена, каждое из которых имеет соответствующую оставшуюся подза- дачу. На основе этого можно выявить оптимальную подструктуру и по- строить уравнение перехода состояния. Когда *s*\[*i*\] = *t*\[*j*\], редактирование текущего символа не требуется.

  - В задаче о расстоянии редактирования состояние зависит от состояний

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