Appunti di studio sugli algoritmi (8) - Nozioni di base sulla programmazione dinamica

Cos'è la programmazione dinamica, quali problemi può risolvere la programmazione dinamica come mezzo, la classificazione della programmazione dinamica e la classificazione di problemi specifici che classificazioni specifiche possono risolvere.

Programmazione dinamica:

Si tratta di un importante paradigma di algoritmo che scompone un problema in una serie di sottoproblemi più piccoli ed evita calcoli ripetuti memorizzando le soluzioni dei sottoproblemi, migliorando così notevolmente l'efficienza in termini di tempo.

Vengono introdotti problemi nella comprensione della programmazione dinamica:

Questo problema viene introdotto nel caso in cui si salgono le scale. Data una scala con n gradini in totale, è possibile salire 1 o 2 gradini per ogni gradino. Quante opzioni ci sono per salire in cima all'edificio?

Analisi: (backtracking violento)

L'obiettivo di questa domanda è trovare il numero di soluzioni,Possiamo considerare di esaurire in maniera esaustiva tutte le possibilità tornando indietro . Nello specifico, immagina di salire le scale come un processo di selezione a più round: partendo da terra, scegliendo uno o due gradini per ogni round, aggiungendo 1 al numero di opzioni ogni volta che raggiungi la cima delle scale e aumentando il numero di opzioni quando raggiungi la cima delle scale.

esempio di codice：


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

Ricerca brutale:

Gli algoritmi di backtracking di solito non smantellano esplicitamente il problema, ma lo trattano come una serie di passaggi decisionali e cercano tutte le possibili soluzioni attraverso l’euristica e la potatura.

Possiamo provare ad analizzare questa domanda dal punto di vista della scomposizione del problema. Supponiamo che ci siano soluzioni dp[i] per salire al livello i-esimo, allora dp[i] è il problema originale e i suoi sottoproblemi includono:

dp[i-1], dp[i-2], dp[1], dp[2]

Dato che possiamo salire solo 1 o 2 gradini in ogni round, quando ci troviamo sulla i-esima scala, potremmo stare solo sui gradini i-1 o i-2 nel round precedente. In altre parole, possiamo passare solo dal livello i-1 o i-2 al livello i-esimo.

Da ciò si può trarre un'importante deduzione: il numero di piani che sono saliti al livello i-1 più il numero di piani che sono saliti al livello i-2 è uguale al numero di piani che sono saliti al livello i -esimo livello. La formula è la seguente:

dp[i] = dp[i-1] + dp[i-2]

Ciò significa che esiste una relazione ricorsiva nel problema dell'arrampicata su edificio e il problema originale può essere risolto costruendo le soluzioni dei sottoproblemi.

Esempio di codice DFS: (cerca)


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

Albero ricorsivo generato da ricorsione violenta：

Per risolvere il suddetto problema di duplicazione nell'albero ricorsivo, il metodo di ricerca in memoria può essere utilizzato per rimuovere un gran numero di sottoalberi identici che vengono costruiti ripetutamente, migliorando così l'efficienza del calcolo. (sottoproblemi sovrapposti）

Ricerca memorizzata:

Per calcolare tutti i sottoproblemi sovrapposti solo una volta, è necessario dichiarare un array nem per registrare la soluzione di ciascun sottoproblema ed eliminare i sottoproblemi sovrapposti durante il processo di ricerca.

Quando dp[i] viene calcolato per la prima volta, viene registrato in nem[i] per un utilizzo successivo.
Quando dp[i] viene ricalcolato, il risultato viene ottenuto direttamente in nem[i] per evitare calcoli ripetuti di sottoproblemi.

Esempio di codice:


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

Dopo la memorizzazione, tutti i sottoproblemi sovrapposti vengono calcolati una sola volta e la complessità temporale è ottimizzata su O(n).

Programmazione dinamica:

La ricerca memorizzata è un metodo "dall'alto verso il basso". Iniziamo dal problema originale (nodo radice) e decomponiamo ricorsivamente i sottoproblemi più grandi in sottoproblemi più piccoli finché non risolviamo il sottoproblema più piccolo conosciuto (nodo foglia). . Successivamente, le soluzioni ai sottoproblemi vengono raccolte strato per strato attraverso il backtracking per costruire una soluzione al problema originale.

Al contrario, la programmazione dinamica è un approccio "dal basso all'alto": inizia con una soluzione al sottoproblema più piccolo e costruisce iterativamente soluzioni a sottoproblemi più grandi fino a ottenere una soluzione al problema originale.

Poiché la programmazione dinamica non include un processo di backtracking, deve essere implementata solo utilizzando l'iterazione del ciclo senza utilizzare la ricorsione.

Esempio di codice: (programmazione dinamica, a partire dal sottoproblema più piccolo)


# 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 di esecuzione (programmazione dinamica):

Analisi: (programmazione dinamica)

Similmente all'algoritmo di backtracking, anche la programmazione dinamica utilizza il concetto di "stato" per rappresentare una fase specifica della risoluzione del problema. Ciascuno stato corrisponde a un sottoproblema e alla corrispondente soluzione ottimale locale. Esempio: Lo stato del problema salire le scale è definito come l'ordine i della scala attuale.

Sulla base di quanto sopra, possiamo riassumere i termini comuni per i termini dinamici:

L'array dp si chiama {tabella dp}, dp[i] rappresenta la soluzione del sottoproblema corrispondente allo stato i
Lo stato corrispondente al sottoproblema minimo (la prima e la seconda scala) è detto stato iniziale
La formula ricorsiva dp[i] = dp[i-1] + dp[i-2] è detta equazione di stato

Ottimizzazione dello spazio:

dp[i] è correlato solo a dp[i-1] e dp[i-2]

Invece di utilizzare un array per memorizzare le soluzioni di tutti i sottoproblemi, sono necessarie solo due variabili per scorrere in avanti.

Esempio di codice:


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

Analisi:

Lo spazio occupato dall'array dp viene omesso e la complessità dello spazio viene ridotta da O(n) a O(1)

Nei problemi di programmazione dinamica, lo stato attuale è correlato solo a un numero limitato di stati precedenti. In questo momento possiamo conservare solo gli stati necessari e risparmiare spazio di memoria attraverso la "riduzione della dimensionalità". . Questa tecnica di ottimizzazione dello spazio è chiamata "variabili rotolanti" o "array rotanti".

Condivisione della tecnologia