Notas de estudo de algoritmo (8) - Noções básicas de 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.

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：


# 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] ;
}

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)


# 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) ;
}

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

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

Exemplo de código:


# 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).

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)


# 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] ;
}

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:

O array dp é denominado {dp table}, dp[i] representa a solução do subproblema correspondente ao estado i
O estado correspondente ao subproblema mínimo (a primeira e a segunda escadas) é chamado de estado inicial
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:


# 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 ;
}

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

Compartilhamento de tecnologia