2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Sisällysluettelo
Ongelmia dynaamisen ohjelmoinnin ymmärtämisessä esitellään:
Analyysi: (väkivaltainen perääntyminen)
Raakavoimarekursiolla luotu rekursiopuu:
Esimerkki koodista: (dynaaminen ohjelmointi, alkaen pienimmästä osaongelmasta)
Suoritusprosessi (dynaaminen ohjelmointi):
Analyysi: (dynaaminen ohjelmointi)
Mitä on dynaaminen ohjelmointi, mitä ongelmia dynaaminen ohjelmointi voi ratkaista välineenä, dynaamisen ohjelmoinnin luokittelu ja tiettyjen ongelmien luokittelu, jotka tietyt luokitukset voivat ratkaista.
Se on tärkeä algoritmiparadigma, joka jakaa ongelman sarjaksi pienempiä osaongelmia ja välttää toistuvia laskelmia tallentamalla osaongelmaratkaisuja, mikä parantaa huomattavasti ajan tehokkuutta.
Tämä ongelma esitellään portaiden kiipeämisen kautta, kun otetaan huomioon portaikko, jossa on yhteensä n askelmaa, voit nousta 1 tai 2 askelmaa jokaisessa vaiheessa. Kuinka monta vaihtoehtoa rakennuksen huipulle on?
Tämän kysymyksen tavoitteena on löytää useita ratkaisuja,Voimme harkita kaikkien mahdollisuuksien tyhjentämistä peruuttamalla . Tarkemmin sanottuna kuvittele portaiden kiipeäminen monen kierroksen valintaprosessina: aloita maasta, valitse yksi tai kaksi askelta jokaisella kierroksella, lisää 1 vaihtoehtojen määrään joka kerta, kun saavut portaiden huipulle, ja lisää vaihtoehtojen määrää, kun pääset portaiden huipulle.
- # 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] ;
- }
Peruutusalgoritmit eivät yleensä pura ongelmaa eksplisiittisesti, vaan käsittelevät ongelmaa sarjana päätöksentekovaiheita ja etsivät kaikkia mahdollisia ratkaisuja heuristiikan ja karsimisen avulla.
Voimme yrittää analysoida tätä kysymystä ongelman hajoamisen näkökulmasta. Oletetaan, että i:nnelle tasolle kiipeämiseen on olemassa dp[i]-ratkaisuja, niin dp[i] on alkuperäinen ongelma ja sen aliongelmia ovat:
dp[i-1], dp[i-2], dp[1], dp[2]
Koska voimme nousta vain 1 tai 2 askelmaa joka kierroksella, kun seisomme i:nnessä portaassa, pystyimme seisomaan vain i-1- tai i-2-portailla edellisellä kierroksella. Toisin sanoen voimme siirtyä vain tasolta i-1 tai i-2 tasolle i.
Tästä voimme tehdä tärkeän johtopäätöksen: i-1 tasolle nousseiden suunnitelmien määrä plus i-2 tasolle noussut suunnitelmien määrä on yhtä suuri kuin i-tasolle noussut suunnitelmien määrä. -taso. Kaava on seuraava:
dp[i] = dp[i-1] + dp[i-2]
Tämä tarkoittaa, että rakennuksen kiipeilyongelmassa on rekursiivinen suhde ja alkuperäinen ongelma voidaan ratkaista rakentamalla osaongelmien ratkaisut.
- # 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) ;
- }
Edellä mainitun rekursiivisen puun monistusongelman ratkaisemiseksi voidaan muistihakumenetelmällä poistaa suuri määrä identtisiä alipuita, joita konstruoidaan toistuvasti, mikä parantaa laskennan tehokkuutta. (päällekkäisiä aliongelmia)
Jos haluat laskea kaikki päällekkäiset aliongelmat vain kerran, sinun on määritettävä taulukko nem tallentamaan kunkin osaongelman ratkaisu ja karsimaan päällekkäiset aliongelmat hakuprosessin aikana.
- # 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) ;
- }
Memoisoinnin jälkeen kaikki päällekkäiset aliongelmat lasketaan vain kerran, ja aikamonimutkaisuus optimoidaan arvoon O(n).
Muistettu haku on "ylhäältä alas" -menetelmä. Aloitamme alkuperäisestä ongelmasta (juurisolmu) ja hajotamme rekursiivisesti pienemmät osaongelmat, kunnes ratkaisemme pienimmän tunnetun aliongelman (lehtisolmu). . Jälkeenpäin aliongelmien ratkaisuja kerätään kerros kerrokselta takaisinperinnön kautta ratkaisun rakentamiseksi alkuperäiseen ongelmaan.
Sitä vastoin dynaaminen ohjelmointi on "alhaalta ylös" -lähestymistapa: aloitetaan ratkaisusta pienimpään osaongelmaan ja rakennetaan iteratiivisesti ratkaisuja suurempiin osaongelmiin, kunnes alkuperäiseen ongelmaan saadaan ratkaisu.
Koska dynaaminen ohjelmointi ei sisällä paluuprosessia, se tarvitsee vain toteuttaa silmukkaiteraatiolla ilman rekursiota.
- # 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] ;
- }
Kuten backtracking-algoritmi, dynaaminen ohjelmointi käyttää myös "tilan" käsitettä edustamaan tiettyä ongelmanratkaisuvaihetta. Jokainen tila vastaa aliongelmaa ja vastaavaa paikallista optimaalista ratkaisua. Esimerkki: Portaiden kiipeämisongelman tila määritellään nykyisen portaikon järjestykseksi i.
Yllä olevan perusteella voimme tiivistää dynaamisten termien yleiset termit:
dp[i] liittyy vain arvoihin dp[i-1] ja dp[i-2]
Sen sijaan, että käyttäisit taulukkoa kaikkien aliongelmien ratkaisujen tallentamiseen, tarvitaan vain kaksi muuttujaa eteenpäin vierimiseen.
- # 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 ;
- }
Taulukon dp viemä tila jätetään pois ja tilan monimutkaisuus pienennetään arvosta O(n) arvoon O(1)
Dynaamisissa ohjelmointiongelmissa nykyinen tila liittyy vain rajoitettuun määrään aikaisempia tiloja. Tällä hetkellä voimme säilyttää vain tarvittavat tilat ja säästää muistitilaa "ulottuvuuden vähentämisen" avulla. . Tätä tilan optimointitekniikkaa kutsutaan "rullaviksi muuttujiksi" tai "rullaviksi taulukoiksi".