2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Inhaltsverzeichnis
Es werden Probleme beim Verständnis der dynamischen Programmierung vorgestellt:
Analyse: (gewalttätiges Zurückverfolgen)
Durch Brute-Force-Rekursion generierter Rekursionsbaum:
Codebeispiel: (dynamische Programmierung, beginnend mit dem kleinsten Teilproblem)
Ausführungsprozess (dynamische Programmierung):
Analyse: (dynamische Programmierung)
Was ist dynamische Programmierung, welche Probleme kann dynamische Programmierung als Mittel lösen, die Klassifizierung dynamischer Programmierung und die Klassifizierung spezifischer Probleme, die durch bestimmte Klassifizierungen gelöst werden können.
Dabei handelt es sich um ein wichtiges Algorithmusparadigma, das ein Problem in eine Reihe kleinerer Teilprobleme zerlegt und wiederholte Berechnungen durch die Speicherung von Teilproblemlösungen vermeidet, wodurch die Zeiteffizienz erheblich verbessert wird.
Dieses Problem entsteht beim Treppensteigen. Bei einer Treppe mit insgesamt n Stufen kann man bei jeder Stufe 1 oder 2 Stufen hinaufsteigen.
Das Ziel dieser Frage besteht darin, die Anzahl der Lösungen zu ermitteln.Wir können darüber nachdenken, alle Möglichkeiten durch einen Rückzieher erschöpfend auszuschöpfen . Stellen Sie sich das Treppensteigen insbesondere als einen mehrrundigen Auswahlprozess vor: Beginnen Sie am Boden, wählen Sie in jeder Runde eine oder zwei Stufen aus, addieren Sie jedes Mal, wenn Sie das obere Ende der Treppe erreichen, 1 zur Anzahl der Optionen und erhöhen Sie die Anzahl der Optionen, wenn Sie erreichen das obere Ende der Treppe.
- # 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] ;
- }
Backtracking-Algorithmen zerlegen das Problem normalerweise nicht explizit, sondern behandeln das Problem als eine Reihe von Entscheidungsschritten und suchen durch Heuristik und Bereinigung nach allen möglichen Lösungen.
Wir können versuchen, diese Frage aus der Perspektive der Problemzerlegung zu analysieren. Angenommen, es gibt dp[i]-Lösungen, um auf die i-te Ebene zu gelangen, dann ist dp[i] das ursprüngliche Problem und seine Unterprobleme umfassen:
dp[i-1],dp[i-2],dp[1],dp[2]
Da wir in jeder Runde nur 1 oder 2 Stufen hinaufsteigen können, konnten wir, wenn wir auf der i-ten Treppe stehen, in der vorherigen Runde nur auf den Stufen i-1 oder i-2 stehen. Mit anderen Worten, wir können nur von der i-1-ten oder i-2-ten Ebene zur i-ten Ebene wechseln.
Daraus können wir eine wichtige Schlussfolgerung ziehen: Die Anzahl der Pläne, die auf die i-1. Ebene aufgestiegen sind, plus die Anzahl der Pläne, die auf die i-2. Ebene aufgestiegen sind, ist gleich der Anzahl der Pläne, die auf die i. Ebene aufgestiegen sind -te Ebene. Die Formel lautet wie folgt:
dp[i] = dp[i-1] + dp[i-2]
Dies bedeutet, dass im Gebäudekletterproblem eine rekursive Beziehung besteht und das ursprüngliche Problem durch die Konstruktion der Lösungen der Unterprobleme gelöst werden kann.
- # 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) ;
- }
Um das oben erwähnte Duplizierungsproblem im rekursiven Baum zu lösen, kann die Speichersuchmethode verwendet werden, um eine große Anzahl identischer Teilbäume zu entfernen, die wiederholt erstellt werden, wodurch die Berechnungseffizienz verbessert wird. (überlappende Teilprobleme)
Um alle überlappenden Teilprobleme nur einmal zu berechnen, müssen Sie ein Array nem deklarieren, um die Lösung jedes Teilproblems aufzuzeichnen und überlappende Teilprobleme während des Suchvorgangs zu bereinigen.
- # 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) ;
- }
Nach dem Auswendiglernen werden alle überlappenden Teilprobleme nur einmal berechnet und die Zeitkomplexität auf O(n) optimiert.
Die gespeicherte Suche ist eine „von oben nach unten“-Methode. Wir beginnen mit dem ursprünglichen Problem (Wurzelknoten) und zerlegen rekursiv größere Unterprobleme in kleinere Unterprobleme, bis wir das kleinste bekannte Unterproblem (Blattknoten) lösen. . Anschließend werden durch Backtracking Schicht für Schicht Lösungen für die Teilprobleme gesammelt, um eine Lösung für das ursprüngliche Problem zu konstruieren.
Im Gegensatz dazu handelt es sich bei der dynamischen Programmierung um einen „Bottom-to-Top“-Ansatz: Beginnend mit einer Lösung für das kleinste Teilproblem und schrittweise Entwicklung von Lösungen für größere Teilprobleme, bis eine Lösung für das ursprüngliche Problem vorliegt.
Da die dynamische Programmierung keinen Backtracking-Prozess beinhaltet, muss sie nur mithilfe einer Schleifeniteration ohne Verwendung einer Rekursion implementiert werden.
- # 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] ;
- }
Ähnlich wie der Backtracking-Algorithmus verwendet auch die dynamische Programmierung das Konzept des „Zustands“, um eine bestimmte Phase der Problemlösung darzustellen. Jeder Zustand entspricht einem Unterproblem und der entsprechenden lokalen optimalen Lösung. Beispiel: Der Status des Treppensteigproblems wird als Ordnung i der aktuellen Treppe definiert.
Basierend auf dem oben Gesagten können wir die allgemeinen Begriffe für dynamische Begriffe zusammenfassen:
dp[i] bezieht sich nur auf dp[i-1] und dp[i-2]
Anstatt ein Array zum Speichern der Lösungen aller Teilprobleme zu verwenden, sind zum Vorwärtsscrollen nur zwei Variablen erforderlich.
- # 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 ;
- }
Der vom Array dp belegte Platz wird weggelassen und die Platzkomplexität wird von O(n) auf O(1) reduziert.
Bei dynamischen Programmierproblemen bezieht sich der aktuelle Zustand nur auf eine begrenzte Anzahl vorheriger Zustände. Zu diesem Zeitpunkt können wir nur die erforderlichen Zustände beibehalten und Speicherplatz durch „Dimensionalitätsreduzierung“ sparen. . Diese Raumoptimierungstechnik wird „rollende Variablen“ oder „rollende Arrays“ genannt.