Compartilhamento de tecnologia

Notas de estudo de algoritmo (8) - Noções básicas de programação dinâmica

2024-07-12

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

Índice

Conteúdo básico:

Programaçao dinamica:

Problemas na compreensão da programação dinâmica são introduzidos:

Análise: (retrocesso violento)

Exemplo de código:

Pesquisa brutal:

Exemplo de código Dfs: (pesquisa)

Árvore de recursão gerada por recursão de força bruta:

Pesquisa memorizada:

Exemplo de código:

Programaçao dinamica:

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)

Otimização de espaço:

Exemplo de código:

Análise:


Conteúdo básico:

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.

Programaçao dinamica:

É 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.

Problemas na compreensão da programação dinâmica são introduzidos:

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.

Análise: (retrocesso violento)

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.

exemplo de código

  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. }

Pesquisa brutal:

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.

Exemplo de código Dfs: (pesquisa)

  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. }

Árvore recursiva gerada por recursão violenta

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

Pesquisa memorizada:

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.

  1. Quando dp[i] é calculado pela primeira vez, ele é registrado em nem[i] para uso posterior.
  2. Quando dp[i] é calculado novamente, o resultado é obtido diretamente em nem[i] para evitar cálculos repetidos de subproblemas.

Exemplo de código:

  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. }

Após a memorização, todos os subproblemas sobrepostos são calculados apenas uma vez e a complexidade do tempo é otimizada para O(n).

Programaçao dinamica:

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.

Exemplo de código: (programação dinâmica, começando pelo menor subproblema)

  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. }

Processo de execução (programação dinâmica):

Análise: (programação dinâmica)

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:

  1. O array dp é denominado {dp table}, dp[i] representa a solução do subproblema correspondente ao estado i
  2. O estado correspondente ao subproblema mínimo (a primeira e a segunda escadas) é chamado de estado inicial
  3. A fórmula recursiva dp[i] = dp[i-1] + dp[i-2] é chamada de equação de estado

Otimização de espaço:

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.

Exemplo de código:

  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. }

Análise:

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".