Обмен технологиями

Заметки по изучению алгоритмов (8) — Основы динамического программирования

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Оглавление

Основное содержание:

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

Возникают проблемы с пониманием динамического программирования:

Анализ: (насильственное отступление)

Пример кода:

Жестокий поиск:

Пример кода Dfs: (поиск)

Дерево рекурсии, созданное методом грубой рекурсии:

Мемоизированный поиск:

Пример кода:

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

Пример кода: (динамическое программирование, начиная с наименьшей подзадачи)

Процесс выполнения (динамическое программирование):

Анализ: (динамическое программирование)

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

Пример кода:

Анализ:


Основное содержание:

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

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

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

Возникают проблемы с пониманием динамического программирования:

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

Анализ: (насильственное отступление)

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

пример кода

  1. # python代码示例
  2. def backrack(choices,state,n,res) :
  3. if state == n :
  4. res[0] += 1
  5. for choice in choices :
  6. if state + choice > n :
  7. continue
  8. backrack(choices,state+choice,n,res)
  9. def climbing_stairs_backrack(n) :
  10. choices = [1,2]
  11. state = 0
  12. res = [0]
  13. backrack(choices,state,n,res)
  14. return res[0]
  15. n = int(input())
  16. print(climbing_stairs_backrack(n))
  1. // c++代码示例
  2. void backrack(vector<int> &choices, int state, int n, vector<int> &res)
  3. {
  4. if (state == n )
  5. {
  6. res[0]++ ;
  7. }
  8. for (auto &choice : choices)
  9. {
  10. if (state + choice > n)
  11. {
  12. continue ;
  13. }
  14. backrack(choices, state + choice, n, res)
  15. }
  16. }
  17. int climbingStairsBackrack(int n)
  18. {
  19. vector<int> choices = {1 , 2 } ;
  20. int state = 0 ;
  21. vector<int> res = [0] ;
  22. backrack(choices, state, n, res) ;
  23. return res[0] ;
  24. }

Жестокий поиск:

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

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

дп[i-1],дп[i-2],дп[1],дп[2]

Поскольку в каждом раунде мы можем подняться только на 1 или 2 ступеньки, то, стоя на i-й лестнице, в предыдущем раунде мы могли стоять только на i-1 или i-2 ступеньках. Другими словами, мы можем перейти только с i-1-го или i-2-го уровня на i-й уровень.

Отсюда можно сделать важный вывод: количество планов, поднявшихся на i-1-й уровень плюс количество планов, поднявшихся на i-2-й уровень, равно количеству планов, поднявшихся на i-й уровень. -й уровень. Формула выглядит следующим образом:

дп[i] = дп[i-1] + дп[i-2]

Это означает, что в задаче подъема по зданию существует рекурсивная связь, и исходную задачу можно решить путем построения решений подзадач.

Пример кода Dfs: (поиск)

  1. # python 代码示例
  2. def dfs(i : int) -> int :
  3. if i == 1 or i == 2 :
  4. return i
  5. count = dfs(i - 1) + dfs(i - 2)
  6. return count
  7. def climbing_stairs_dfs(n : int) -> int :
  8. retunr dfs(n)
  1. // c++ 代码示例
  2. int dfs(int i)
  3. {
  4. if (i == 1 || i == 2)
  5. {
  6. return i ;
  7. }
  8. int count = dfs(i - 1) + dfs(i - 2);
  9. return count ;
  10. }
  11. int climbingStairsDFS(int n)
  12. {
  13. retunr dfs(n) ;
  14. }

Рекурсивное дерево, созданное с помощью сильной рекурсии

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

Мемоизированный поиск:

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

  1. Когда dp[i] вычисляется впервые, он записывается в nem[i] для последующего использования.
  2. При повторном вычислении dp[i] результат получается непосредственно в nem[i], чтобы избежать повторных вычислений подзадач.

Пример кода:

  1. # python 代码示例
  2. def dfs(i : int, mem : list[int]) -> int :
  3. if i == 1 or i == 2 :
  4. return i
  5. if mem[i] != -1 :
  6. return mem[i]
  7. count = dfs(i - 1, mem) + dfs(i - 2, mem)
  8. # 记录dfs(i)
  9. mem[i] = count
  10. return count
  11. def climbing_stairs_dfs_mem(n : int) -> int :
  12. mem = [-1] * (n + 1)
  13. return dfs(n, mem)
  1. // c++ 代码示例
  2. int dfs(int i, vector<int> &mem)
  3. {
  4. if (i == 1 || i == 2)
  5. {
  6. return i ;
  7. }
  8. if (mem != -1)
  9. {
  10. return mem[i] ;
  11. }
  12. int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
  13. mem[i] = count ;
  14. return count ;
  15. }
  16. int climbingStairsDFSMem(int n)
  17. {
  18. vector<int> mem(n + 1, -1) ;
  19. return dfs(n, mem) ;
  20. }

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

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

Мемоизированный поиск — это метод «сверху вниз». Мы начинаем с исходной проблемы (корневой узел) и рекурсивно разлагаем более крупные подзадачи на более мелкие подзадачи, пока не решим наименьшую известную подзадачу (листовой узел). . После этого решения подзадач собираются слой за слоем посредством обратного отслеживания, чтобы построить решение исходной проблемы.

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

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

Пример кода: (динамическое программирование, начиная с наименьшей подзадачи)

  1. # python 代码示例
  2. def clibing_stairs_dp(n) :
  3. if n == 1 or n == 2 :
  4. return n
  5. dp = [0] * (n + 1)
  6. dp[1], dp[2] = 1, 2
  7. for i in range(3,n + 1) :
  8. dp[i] = dp[i-1] + dp[i- 2]
  9. return dp[n]
  1. // c++ 代码示例
  2. int climbingStairsDP(int n)
  3. {
  4. if (n == 1 || n == 2)
  5. {
  6. retunr n ;
  7. }
  8. vector<int> dp(n + 1, -1) ;
  9. dp[1] = 1 ;
  10. dp[2] = 2 ;
  11. for (int i = 3 ; i <= n ; i++)
  12. {
  13. dp[i] = dp[i - 1] + dp[i- 2] ;
  14. }
  15. return dp[n] ;
  16. }

Процесс выполнения (динамическое программирование):

Анализ: (динамическое программирование)

Подобно алгоритму обратного отслеживания, динамическое программирование также использует концепцию «состояния» для обозначения определенного этапа решения проблемы. Каждое состояние соответствует подзадаче и соответствующему локальному оптимальному решению. Пример: Статус проблемы подъема по лестнице определяется как порядок i текущей лестницы.

Основываясь на вышеизложенном, мы можем обобщить общие термины для динамических терминов:

  1. Массив dp называется {dp table}, dp[i] представляет собой решение подзадачи, соответствующей состоянию i.
  2. Состояние, соответствующее минимальной подзадаче (первая и вторая ступеньки), называется начальным состоянием.
  3. Рекурсивная формула dp[i] = dp[i-1] + dp[i-2] называется уравнением состояния

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

dp[i] относится только к dp[i-1] и dp[i-2]

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

Пример кода:

  1. # python 代码示例
  2. def clibing_stairs_dp_comp(n) :
  3. if n == 1 or n == 2 :
  4. return n
  5. a, b = 1, 2
  6. for _ in range(3, n + 1) :
  7. a, b = b , a + b
  8. return b
  1. // c++ 代码示例
  2. int climbingStairsComp(int n)
  3. {
  4. if (n == 1 || n == 2)
  5. {
  6. return n ;
  7. }
  8. int a = 1 , b = 2 ;
  9. for (int i = 3 ; i <= n ; i++)
  10. {
  11. int temp = b ;
  12. b = a + b ;
  13. a = temp ;
  14. }
  15. return b ;
  16. }

Анализ:

Пространство, занимаемое массивом dp, опускается, а сложность пространства снижается с O(n) до O(1).

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