Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Tabla de contenido
Se introducen problemas para comprender la programación dinámica:
Análisis: (retroceso violento)
Ejemplo de código DFS: (búsqueda)
Árbol de recursividad generado por recursividad de fuerza bruta:
Ejemplo de código: (programación dinámica, comenzando desde el subproblema más pequeño)
Proceso de ejecución (programación dinámica):
Análisis: (programación dinámica)
Qué es la programación dinámica, qué problemas puede resolver la programación dinámica como medio, la clasificación de la programación dinámica y la clasificación de problemas específicos que las clasificaciones específicas pueden resolver.
Es un paradigma algorítmico importante que descompone un problema en una serie de subproblemas más pequeños y evita cálculos repetidos al almacenar soluciones de subproblemas, lo que mejora en gran medida la eficiencia del tiempo.
Este problema se introduce a través del caso de subir escaleras. Dada una escalera con n escalones en total, puedes subir 1 o 2 escalones en cada escalón. ¿Cuántas opciones hay para subir a la cima del edificio?
El objetivo de esta pregunta es encontrar el número de soluciones,Podemos considerar agotar exhaustivamente todas las posibilidades retrocediendo . Específicamente, imagine subir escaleras como un proceso de selección de múltiples rondas: comenzar desde el suelo, elegir uno o dos escalones en cada ronda, agregar 1 al número de opciones cada vez que llegue a la cima de las escaleras y aumentar el número de opciones cuando Llegas a lo alto de las escaleras.
- # 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] ;
- }
Los algoritmos de retroceso generalmente no desmantelan explícitamente el problema, sino que lo tratan como una serie de pasos de toma de decisiones y buscan todas las soluciones posibles mediante heurísticas y poda.
Podemos intentar analizar esta cuestión desde la perspectiva de la descomposición del problema. Supongamos que hay soluciones dp [i] para subir al nivel i-ésimo, entonces dp [i] es el problema original y sus subproblemas incluyen:
dp[i-1], dp[i-2], dp[1], dp[2]
Como solo podemos subir 1 o 2 escalones en cada ronda, cuando nos paramos en la i-ésima escalera, solo pudimos pararnos en los escalones i-1 o i-2 de la ronda anterior. En otras palabras, solo podemos pasar del nivel i-1 o i-2 al nivel i-ésimo.
De esto, podemos sacar una inferencia importante: el número de planes que han subido al nivel i-1 más el número de planes que han subido al nivel i-2 es igual al número de planes que han subido al i -ésimo nivel. La fórmula es la siguiente:
dp[i] = dp[i-1] + dp[i-2]
Esto significa que existe una relación recursiva en el problema de escalada de edificios y el problema original se puede resolver construyendo las soluciones de los subproblemas.
- # 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) ;
- }
Para resolver el problema de duplicación mencionado anteriormente en el árbol recursivo, se puede utilizar el método de búsqueda de memoria para eliminar una gran cantidad de subárboles idénticos que se construyen repetidamente, mejorando así la eficiencia del cálculo. (subproblemas superpuestos)
Para calcular todos los subproblemas superpuestos solo una vez, debe declarar una matriz nem para registrar la solución de cada subproblema y podar los subproblemas superpuestos durante el proceso de búsqueda.
- # 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) ;
- }
Después de la memorización, todos los subproblemas superpuestos se calculan solo una vez y la complejidad del tiempo se optimiza a O (n).
La búsqueda memorizada es un método "de arriba a abajo". Partimos del problema original (nodo raíz) y descomponemos recursivamente los subproblemas más grandes en subproblemas más pequeños hasta resolver el subproblema más pequeño conocido (nodo hoja). . Luego, las soluciones a los subproblemas se recopilan capa por capa mediante un retroceso para construir una solución al problema original.
Por el contrario, la programación dinámica es un enfoque "de abajo hacia arriba": comienza con una solución al subproblema más pequeño y construye iterativamente soluciones para subproblemas más grandes hasta obtener una solución al problema original.
Dado que la programación dinámica no incluye un proceso de retroceso, solo debe implementarse mediante iteración de bucle sin utilizar recursividad.
- # 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] ;
- }
Al igual que el algoritmo de retroceso, la programación dinámica también utiliza el concepto de "estado" para representar una etapa específica de la resolución del problema. Cada estado corresponde a un subproblema y la solución óptima local correspondiente. Ejemplo: El estado del problema de subir escaleras se define como el orden i de la escalera actual.
Con base en lo anterior, podemos resumir los términos comunes para términos dinámicos:
dp[i] solo está relacionado con dp[i-1] y dp[i-2]
En lugar de utilizar una matriz para almacenar las soluciones de todos los subproblemas, sólo se necesitan dos variables para desplazarse hacia adelante.
- # 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 ;
- }
Se omite el espacio ocupado por la matriz dp y la complejidad del espacio se reduce de O (n) a O (1)
En los problemas de programación dinámica, el estado actual solo está relacionado con un número limitado de estados anteriores. En este momento, solo podemos retener los estados necesarios y ahorrar espacio en la memoria mediante la "reducción de dimensionalidad". . Esta técnica de optimización del espacio se denomina "variables rodantes" o "matrices rodantes".