Anmerkungen zum Algorithmusstudium (8) – Grundlagen der dynamischen 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.

Dynamische Programmierung:

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.

Es werden Probleme beim Verständnis der dynamischen Programmierung vorgestellt:

Dieses Problem entsteht beim Treppensteigen. Bei einer Treppe mit insgesamt n Stufen kann man bei jeder Stufe 1 oder 2 Stufen hinaufsteigen.

Analyse: (gewalttätiges Zurückverfolgen)

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.

Codebeispiel：


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

Brutale Suche:

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.

DFS-Codebeispiel: (Suche)


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

Rekursiver Baum, der durch heftige Rekursion erzeugt wird：

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）

Auswendig gelernte Suche:

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.

Wenn dp[i] zum ersten Mal berechnet wird, wird es zur späteren Verwendung in nem[i] aufgezeichnet.
Wenn dp[i] erneut berechnet wird, wird das Ergebnis direkt in nem[i] erhalten, um wiederholte Berechnungen von Teilproblemen zu vermeiden.

Codebeispiel:


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

Dynamische Programmierung:

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.

Codebeispiel: (dynamische Programmierung, beginnend mit dem kleinsten Teilproblem)


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

Ausführungsprozess (dynamische Programmierung):

Analyse: (dynamische Programmierung)

Ä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:

Das Array dp heißt {dp table}, dp [i] stellt die Lösung des Teilproblems dar, das dem Zustand i entspricht
Der Zustand, der dem minimalen Teilproblem entspricht (erste und zweite Treppe), wird als Anfangszustand bezeichnet
Die rekursive Formel dp[i] = dp[i-1] + dp[i-2] wird Zustandsgleichung genannt

Platzoptimierung:

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.

Codebeispiel:


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

Analyse:

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.

Technologieaustausch