Σημειώσεις Μελέτης Αλγορίθμου (8) - Βασικά στοιχεία Δυναμικού Προγραμματισμού

Τι είναι ο δυναμικός προγραμματισμός, ποια προβλήματα μπορεί να λύσει ο δυναμικός προγραμματισμός ως μέσο, η ταξινόμηση του δυναμικού προγραμματισμού και η ταξινόμηση συγκεκριμένων προβλημάτων που μπορούν να λύσουν συγκεκριμένες ταξινομήσεις.

Δυναμικός προγραμματισμός:

Είναι ένα σημαντικό παράδειγμα αλγορίθμου που αναλύει ένα πρόβλημα σε μια σειρά από μικρότερα υποπροβλήματα και αποφεύγει τους επαναλαμβανόμενους υπολογισμούς αποθηκεύοντας λύσεις υποπροβλημάτων, βελτιώνοντας έτσι σημαντικά τη χρονική απόδοση.

Παρουσιάζονται προβλήματα στην κατανόηση του δυναμικού προγραμματισμού:

Αυτό το πρόβλημα εισάγεται μέσω της περίπτωσης αναρρίχησης σκαλοπατιών Δεδομένου ότι μια σκάλα με n συνολικά σκαλοπάτια, μπορείτε να ανεβείτε 1 ή 2 σκαλοπάτια σε κάθε σκαλί.

Ανάλυση: (βίαιη οπισθοδρόμηση)

Ο στόχος αυτής της ερώτησης είναι να βρεθεί ο αριθμός των λύσεων,Μπορούμε να εξετάσουμε εξαντλητικά όλες τις πιθανότητες κάνοντας πίσω . Συγκεκριμένα, φανταστείτε την ανάβαση σκάλας ως μια διαδικασία επιλογής πολλαπλών γύρων: ξεκινώντας από το έδαφος, επιλέγοντας ένα ή δύο βήματα κάθε γύρο, προσθέτοντας 1 στον αριθμό των επιλογών κάθε φορά που φτάνετε στην κορυφή της σκάλας και αυξάνοντας τον αριθμό των επιλογών όταν φτάνεις στην κορυφή της σκάλας.

παράδειγμα κώδικα：


# 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 συνήθως δεν διαλύουν ρητά το πρόβλημα, αλλά αντιμετωπίζουν το πρόβλημα ως μια σειρά βημάτων λήψης αποφάσεων και αναζητούν όλες τις πιθανές λύσεις μέσω ευρετικών και περικοπών.

Μπορούμε να προσπαθήσουμε να αναλύσουμε αυτό το ερώτημα από την προοπτική της αποσύνθεσης του προβλήματος. Ας υποθέσουμε ότι υπάρχουν λύσεις dp[i] για να ανεβείτε στο i-ο επίπεδο, τότε το dp[i] είναι το αρχικό πρόβλημα και τα υποπροβλήματά του περιλαμβάνουν:

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

Δεδομένου ότι μπορούμε να ανεβαίνουμε μόνο 1 ή 2 σκαλοπάτια σε κάθε γύρο, όταν στεκόμαστε στην i-η σκάλα, μπορούσαμε να σταθούμε μόνο στα σκαλιά i-1 ή i-2 στον προηγούμενο γύρο. Με άλλα λόγια, μπορούμε να μετακινηθούμε μόνο από το i-1ο ή i-2ο επίπεδο στο i-ο επίπεδο.

Από αυτό, μπορούμε να βγάλουμε ένα σημαντικό συμπέρασμα: ο αριθμός των σχεδίων που έχουν ανέβει στο επίπεδο i-1ο συν ο αριθμός των σχεδίων που έχουν ανέβει στο επίπεδο i-2ο είναι ίσος με τον αριθμό των σχεδίων που έχουν ανέβει στο i -ο επίπεδο. Ο τύπος έχει ως εξής:

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

Αυτό σημαίνει ότι υπάρχει μια αναδρομική σχέση στο πρόβλημα αναρρίχησης κτιρίου και το αρχικό πρόβλημα μπορεί να λυθεί με την κατασκευή των λύσεων των υποπροβλημάτων.

Παράδειγμα κώδικα Dfs: (αναζήτηση)


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

Αναδρομικό δέντρο που δημιουργείται από βίαιη αναδρομή：

Για την επίλυση του προαναφερθέντος προβλήματος διπλασιασμού στο αναδρομικό δέντρο, η μέθοδος αναζήτησης μνήμης μπορεί να χρησιμοποιηθεί για την αφαίρεση μεγάλου αριθμού πανομοιότυπων υποδέντρων που κατασκευάζονται επανειλημμένα, βελτιώνοντας έτσι την απόδοση υπολογισμού. (επικαλυπτόμενα υποπροβλήματα）

Απομνημονευμένη αναζήτηση:

Για να υπολογίσετε όλα τα επικαλυπτόμενα υποπροβλήματα μόνο μία φορά, θα πρέπει να δηλώσετε ένα nem πίνακα για να καταγράψετε τη λύση κάθε υποπροβλήματος και να κλαδέψετε τα επικαλυπτόμενα υποπροβλήματα κατά τη διαδικασία αναζήτησης.

Όταν το dp[i] υπολογίζεται για πρώτη φορά, καταγράφεται σε nem[i] για μεταγενέστερη χρήση.
Όταν υπολογιστεί ξανά το dp[i], το αποτέλεσμα λαμβάνεται απευθείας σε nem[i] για να αποφευχθούν οι επαναλαμβανόμενοι υπολογισμοί των υποπροβλημάτων.

Παράδειγμα κώδικα:


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

Μετά την απομνημόνευση, όλα τα επικαλυπτόμενα υποπροβλήματα υπολογίζονται μόνο μία φορά και η χρονική πολυπλοκότητα βελτιστοποιείται σε O(n).

Δυναμικός προγραμματισμός:

Η απομνημονευμένη αναζήτηση είναι μια μέθοδος "από πάνω προς τα κάτω" Ξεκινάμε από το αρχικό πρόβλημα (κόμβος ρίζας) και αποσυνθέτουμε αναδρομικά τα μεγαλύτερα υποπροβλήματα σε μικρότερα υποπροβλήματα μέχρι να λύσουμε το μικρότερο γνωστό υποπρόβλημα (φύλλο). . Στη συνέχεια, οι λύσεις στα υποπροβλήματα συλλέγονται στρώμα προς στρώμα μέσω backtracking για να κατασκευαστεί μια λύση στο αρχικό πρόβλημα.

Αντίθετα, ο δυναμικός προγραμματισμός είναι μια προσέγγιση «από κάτω προς τα πάνω»: ξεκινώντας με μια λύση στο μικρότερο υποπρόβλημα και επαναλαμβανόμενη δημιουργία λύσεων σε μεγαλύτερα υποπροβλήματα μέχρι να επιτευχθεί μια λύση στο αρχικό πρόβλημα.

Δεδομένου ότι ο δυναμικός προγραμματισμός δεν περιλαμβάνει μια διαδικασία backtracking, χρειάζεται μόνο να υλοποιηθεί χρησιμοποιώντας επανάληψη βρόχου χωρίς τη χρήση αναδρομής.

Παράδειγμα κώδικα: (δυναμικός προγραμματισμός, ξεκινώντας από το μικρότερο υποπρόβλημα)


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

Διαδικασία εκτέλεσης (δυναμικός προγραμματισμός):

Ανάλυση: (δυναμικός προγραμματισμός)

Παρόμοια με τον αλγόριθμο backtracking, ο δυναμικός προγραμματισμός χρησιμοποιεί επίσης την έννοια της "κατάστασης" για να αναπαραστήσει ένα συγκεκριμένο στάδιο επίλυσης προβλημάτων Κάθε κατάσταση αντιστοιχεί σε ένα υποπρόβλημα και στην αντίστοιχη τοπική βέλτιστη λύση. Παράδειγμα: Η κατάσταση του προβλήματος αναρρίχησης σκάλας ορίζεται ως η σειρά i της τρέχουσας σκάλας.

Με βάση τα παραπάνω, μπορούμε να συνοψίσουμε τους κοινούς όρους για δυναμικούς όρους:

Ο πίνακας dp ονομάζεται {dp table}, το dp[i] αντιπροσωπεύει τη λύση στο υποπρόβλημα που αντιστοιχεί στην κατάσταση i
Η κατάσταση που αντιστοιχεί στο ελάχιστο υποπρόβλημα (η πρώτη και η δεύτερη σκάλα) ονομάζεται αρχική κατάσταση
Ο αναδρομικός τύπος dp[i] = dp[i-1] + dp[i-2] ονομάζεται εξίσωση κατάστασης

Βελτιστοποίηση χώρου:

Το dp[i] σχετίζεται μόνο με τα dp[i-1] και dp[i-2]

Αντί να χρησιμοποιείτε έναν πίνακα για την αποθήκευση των λύσεων σε όλα τα υποπροβλήματα, χρειάζονται μόνο δύο μεταβλητές για κύλιση προς τα εμπρός.

Παράδειγμα κώδικα:


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

Ανάλυση:

Ο χώρος που καταλαμβάνει ο πίνακας dp παραλείπεται και η πολυπλοκότητα του χώρου μειώνεται από O(n) σε O(1)

Σε προβλήματα δυναμικού προγραμματισμού, η τρέχουσα κατάσταση σχετίζεται μόνο με έναν περιορισμένο αριθμό προηγούμενων καταστάσεων Αυτή τη στιγμή, μπορούμε να διατηρήσουμε μόνο τις απαραίτητες καταστάσεις και να εξοικονομήσουμε χώρο στη μνήμη μέσω "μείωσης διαστάσεων". . Αυτή η τεχνική βελτιστοποίησης χώρου ονομάζεται "κυλιόμενες μεταβλητές" ή "κυλιόμενες συστοιχίες".

Κοινή χρήση τεχνολογίας