minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Índice
Problemas na compreensão da programação dinâmica são introduzidos:
Análise: (retrocesso violento)
Exemplo de código Dfs: (pesquisa)
Árvore de recursão gerada por recursão de força bruta:
Exemplo de código: (programação dinâmica, começando pelo menor subproblema)
Processo de execução (programação dinâmica):
Análise: (programação dinâmica)
O que é programação dinâmica, quais problemas a programação dinâmica pode resolver como meio, a classificação da programação dinâmica e a classificação de problemas específicos que classificações específicas podem resolver.
É um importante paradigma de algoritmo que decompõe um problema em uma série de subproblemas menores e evita cálculos repetidos, armazenando soluções de subproblemas, melhorando muito a eficiência do tempo.
Este problema é apresentado através do caso de subir escadas. Dada uma escada com n degraus no total, você pode subir 1 ou 2 degraus em cada degrau.
O objetivo desta questão é encontrar o número de soluções,Podemos considerar esgotar exaustivamente todas as possibilidades retrocedendo . Especificamente, imagine subir escadas como um processo de seleção de múltiplas rodadas: começando do chão, escolhendo um ou dois degraus em cada rodada, adicionando 1 ao número de opções sempre que chegar ao topo da escada e aumentando o número de opções quando você chega ao topo da escada.
- # 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] ;
- }
Algoritmos de retrocesso geralmente não desmontam explicitamente o problema, mas tratam o problema como uma série de etapas de tomada de decisão e buscam todas as soluções possíveis por meio de heurística e poda.
Podemos tentar analisar esta questão do ponto de vista da decomposição do problema. Suponha que existam soluções dp[i] para subir ao i-ésimo nível, então dp[i] é o problema original e seus subproblemas incluem:
dp[i-1], dp[i-2], dp[1], dp[2]
Como só podemos subir 1 ou 2 degraus em cada rodada, quando estivermos na i-ésima escada, só poderíamos subir nos i-1 ou i-2 degraus da rodada anterior. Em outras palavras, só podemos passar do i-1º ou i-2º nível para o i-ésimo nível.
Disto podemos tirar uma inferência importante: o número de planos que subiram para o i-1º nível mais o número de planos que subiram para o i-2º nível é igual ao número de planos que subiram para o i-2º nível. -º nível. A fórmula é a seguinte:
dp[i] = dp[i-1] + dp[i-2]
Isso significa que existe uma relação recursiva no problema de escalada de edifícios, e o problema original pode ser resolvido construindo as soluções dos 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 o problema de duplicação acima mencionado na árvore recursiva, o método de busca de memória pode ser usado para remover um grande número de subárvores idênticas que são construídas repetidamente, melhorando assim a eficiência do cálculo. (subproblemas sobrepostos)
Para calcular todos os subproblemas sobrepostos apenas uma vez, você precisa declarar um array nem para registrar a solução de cada subproblema e remover subproblemas sobrepostos durante o processo de pesquisa.
- # 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) ;
- }
Após a memorização, todos os subproblemas sobrepostos são calculados apenas uma vez e a complexidade do tempo é otimizada para O(n).
A pesquisa memorizada é um método "de cima para baixo". Começamos a partir do problema original (nó raiz) e decompomos recursivamente subproblemas maiores em subproblemas menores até resolvermos o menor subproblema conhecido (nó folha). . Posteriormente, as soluções para os subproblemas são coletadas camada por camada por meio de retrocesso para construir uma solução para o problema original.
Em contraste, a programação dinâmica é uma abordagem "de baixo para cima": começando com uma solução para o menor subproblema e construindo iterativamente soluções para subproblemas maiores até que uma solução para o problema original seja obtida.
Como a programação dinâmica não inclui um processo de retrocesso, ela só precisa ser implementada usando iteração de loop sem usar recursão.
- # 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] ;
- }
Semelhante ao algoritmo de retrocesso, a programação dinâmica também utiliza o conceito de "estado" para representar um estágio específico de resolução de problemas. Cada estado corresponde a um subproblema e à solução ótima local correspondente. Exemplo: O status do problema de subir escadas é definido como a ordem i da escada atual.
Com base no exposto, podemos resumir os termos comuns para termos dinâmicos:
dp[i] está relacionado apenas a dp[i-1] e dp[i-2]
Em vez de usar um array para armazenar as soluções para todos os subproblemas, são necessárias apenas duas variáveis para avançar.
- # 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 ;
- }
O espaço ocupado pelo array dp é omitido e a complexidade do espaço é reduzida de O(n) para O(1)
Em problemas de programação dinâmica, o estado atual está relacionado apenas a um número limitado de estados anteriores. Neste momento, só podemos reter os estados necessários e economizar espaço de memória através da “redução da dimensionalidade”. . Esta técnica de otimização de espaço é chamada de "variáveis rolantes" ou "matrizes rolantes".