моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Оглавление
Динамическое программирование:
Возникают проблемы с пониманием динамического программирования:
Анализ: (насильственное отступление)
Дерево рекурсии, созданное методом грубой рекурсии:
Динамическое программирование:
Пример кода: (динамическое программирование, начиная с наименьшей подзадачи)
Процесс выполнения (динамическое программирование):
Анализ: (динамическое программирование)
Что такое динамическое программирование, какие проблемы можно решить с помощью динамического программирования, классификация динамического программирования и классификация конкретных проблем, которые могут решить конкретные классификации.
Это важная парадигма алгоритма, которая разлагает проблему на ряд более мелких подзадач и позволяет избежать повторных вычислений за счет сохранения решений подзадач, что значительно повышает эффективность использования времени.
Эта задача возникает в случае подъема по лестнице. Всего у лестницы n ступеней, и на каждой ступеньке можно подняться на 1 или 2 ступеньки. Сколько существует вариантов подняться на вершину здания?
Цель этого вопроса — найти количество решений,Мы можем рассмотреть возможность исчерпывающего исчерпания всех возможностей, отступив назад. . В частности, представьте себе подъем по лестнице как процесс выбора, состоящий из нескольких раундов: начиная с земли, выбирая одну или две ступеньки в каждом раунде, добавляя 1 к числу вариантов каждый раз, когда вы достигаете вершины лестницы, и увеличивая количество вариантов, когда Вы достигаете вершины лестницы.
- # python代码示例
- def backrack(choices,state,n,res) :
- if state == n :
- res[0] += 1
- for choice in choices :
- if state + choice > n :
- continue
- backrack(choices,state+choice,n,res)
- def climbing_stairs_backrack(n) :
- choices = [1,2]
- state = 0
- res = [0]
- backrack(choices,state,n,res)
- return res[0]
- n = int(input())
- print(climbing_stairs_backrack(n))
- // c++代码示例
- void backrack(vector<int> &choices, int state, int n, vector<int> &res)
- {
- if (state == n )
- {
- res[0]++ ;
- }
- for (auto &choice : choices)
- {
- if (state + choice > n)
- {
- continue ;
- }
- backrack(choices, state + choice, n, res)
- }
- }
-
- int climbingStairsBackrack(int n)
- {
- vector<int> choices = {1 , 2 } ;
- int state = 0 ;
- vector<int> res = [0] ;
- backrack(choices, state, n, res) ;
- return res[0] ;
- }
Алгоритмы поиска с возвратом обычно не устраняют проблему явно, а рассматривают ее как серию шагов принятия решений и ищут все возможные решения посредством эвристики и сокращения.
Мы можем попытаться проанализировать этот вопрос с точки зрения декомпозиции проблемы. Предположим, что существуют решения 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]
Это означает, что в задаче подъема по зданию существует рекурсивная связь, и исходную задачу можно решить путем построения решений подзадач.
- # python 代码示例
- def dfs(i : int) -> int :
- if i == 1 or i == 2 :
- return i
- count = dfs(i - 1) + dfs(i - 2)
- return count
- def climbing_stairs_dfs(n : int) -> int :
- retunr dfs(n)
- // c++ 代码示例
- int dfs(int i)
- {
- if (i == 1 || i == 2)
- {
- return i ;
- }
- int count = dfs(i - 1) + dfs(i - 2);
- return count ;
- }
- int climbingStairsDFS(int n)
- {
- retunr dfs(n) ;
- }
Для решения упомянутой выше проблемы дублирования в рекурсивном дереве можно использовать метод поиска по памяти для удаления большого количества повторяющихся одинаковых поддеревьев, тем самым повышая эффективность вычислений. (перекрывающиеся подзадачи)
Чтобы вычислить все перекрывающиеся подзадачи только один раз, вам необходимо объявить массив nem для записи решения каждой подзадачи и исключить перекрывающиеся подзадачи в процессе поиска.
- # python 代码示例
- def dfs(i : int, mem : list[int]) -> int :
- if i == 1 or i == 2 :
- return i
- if mem[i] != -1 :
- return mem[i]
- count = dfs(i - 1, mem) + dfs(i - 2, mem)
- # 记录dfs(i)
- mem[i] = count
- return count
- def climbing_stairs_dfs_mem(n : int) -> int :
- mem = [-1] * (n + 1)
- return dfs(n, mem)
- // c++ 代码示例
- int dfs(int i, vector<int> &mem)
- {
- if (i == 1 || i == 2)
- {
- return i ;
- }
- if (mem != -1)
- {
- return mem[i] ;
- }
- int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
- mem[i] = count ;
- return count ;
- }
- int climbingStairsDFSMem(int n)
- {
- vector<int> mem(n + 1, -1) ;
- return dfs(n, mem) ;
- }
После мемоизации все перекрывающиеся подзадачи вычисляются только один раз, а временная сложность оптимизируется до O(n).
Мемоизированный поиск — это метод «сверху вниз». Мы начинаем с исходной проблемы (корневой узел) и рекурсивно разлагаем более крупные подзадачи на более мелкие подзадачи, пока не решим наименьшую известную подзадачу (листовой узел). . После этого решения подзадач собираются слой за слоем посредством обратного отслеживания, чтобы построить решение исходной проблемы.
Напротив, динамическое программирование представляет собой подход «снизу вверх»: начиная с решения наименьшей подзадачи и итеративно создавая решения для более крупных подзадач, пока не будет получено решение исходной проблемы.
Поскольку динамическое программирование не включает в себя процесс возврата, его необходимо реализовать только с помощью итерации цикла без использования рекурсии.
- # python 代码示例
- def clibing_stairs_dp(n) :
- if n == 1 or n == 2 :
- return n
- 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]
- // c++ 代码示例
-
- int climbingStairsDP(int n)
- {
- if (n == 1 || n == 2)
- {
- retunr n ;
- }
- vector<int> dp(n + 1, -1) ;
- dp[1] = 1 ;
- dp[2] = 2 ;
- for (int i = 3 ; i <= n ; i++)
- {
- dp[i] = dp[i - 1] + dp[i- 2] ;
- }
- return dp[n] ;
- }
Подобно алгоритму обратного отслеживания, динамическое программирование также использует концепцию «состояния» для обозначения определенного этапа решения проблемы. Каждое состояние соответствует подзадаче и соответствующему локальному оптимальному решению. Пример: Статус проблемы подъема по лестнице определяется как порядок i текущей лестницы.
Основываясь на вышеизложенном, мы можем обобщить общие термины для динамических терминов:
dp[i] относится только к dp[i-1] и dp[i-2]
Вместо использования массива для хранения решений всех подзадач для прокрутки вперед необходимы всего две переменные.
- # python 代码示例
- def clibing_stairs_dp_comp(n) :
- 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
- // c++ 代码示例
- int climbingStairsComp(int n)
- {
- if (n == 1 || n == 2)
- {
- return n ;
- }
- int a = 1 , b = 2 ;
- for (int i = 3 ; i <= n ; i++)
- {
- int temp = b ;
- b = a + b ;
- a = temp ;
- }
- return b ;
- }
Пространство, занимаемое массивом dp, опускается, а сложность пространства снижается с O(n) до O(1).
В задачах динамического программирования текущее состояние связано только с ограниченным числом предыдущих состояний. В настоящее время мы можем сохранять только необходимые состояния и экономить пространство памяти за счет «уменьшения размерности». . Этот метод оптимизации пространства называется «скользящими переменными» или «скользящими массивами».