le mie informazioni di contatto
Posta[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Sommario
Vengono introdotti problemi nella comprensione della programmazione dinamica:
Analisi: (backtracking violento)
Esempio di codice DFS: (cerca)
Albero di ricorsione generato dalla ricorsione a forza bruta:
Esempio di codice: (programmazione dinamica, a partire dal sottoproblema più piccolo)
Processo di esecuzione (programmazione dinamica):
Analisi: (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.
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.
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?
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.
- # 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] ;
- }
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.
- # 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) ;
- }
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)
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.
- # 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).
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.
- # 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] ;
- }
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:
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.
- # 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 ;
- }
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".