Notes d'étude des algorithmes (8) - Bases de la programmation dynamique

Qu'est-ce que la programmation dynamique, quels problèmes la programmation dynamique peut-elle résoudre comme moyen, la classification de la programmation dynamique et la classification des problèmes spécifiques que des classifications spécifiques peuvent résoudre.

Programmation dynamique:

Il s'agit d'un paradigme algorithmique important qui décompose un problème en une série de sous-problèmes plus petits et évite les calculs répétés en stockant les solutions des sous-problèmes, améliorant ainsi considérablement l'efficacité du temps.

Des problèmes de compréhension de la programmation dynamique sont introduits :

Ce problème est introduit dans le cas de la montée d'escaliers. Étant donné un escalier comportant n marches au total, vous pouvez monter 1 ou 2 marches à chaque marche. Combien y a-t-il d'options pour monter jusqu'au sommet du bâtiment ?

Analyse : (retour en arrière violent)

Le but de cette question est de trouver le nombre de solutions,On peut envisager d’épuiser exhaustivement toutes les possibilités en faisant marche arrière . Plus précisément, imaginez monter les escaliers comme un processus de sélection à plusieurs tours : en commençant par le sol, en choisissant une ou deux marches à chaque tour, en ajoutant 1 au nombre d'options à chaque fois que vous atteignez le haut de l'escalier, et en augmentant le nombre d'options lorsque vous montez les escaliers. vous atteignez le haut des escaliers.

exemple de code：


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

Recherche brutale :

Les algorithmes de backtracking ne démantelent généralement pas explicitement le problème, mais traitent le problème comme une série d’étapes de prise de décision et recherchent toutes les solutions possibles par le biais d’heuristiques et d’élagage.

Nous pouvons tenter d’analyser cette question sous l’angle de la décomposition du problème. Supposons qu'il existe des solutions dp[i] pour grimper au i-ème niveau, alors dp[i] est le problème d'origine, et ses sous-problèmes incluent :

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

Puisque nous ne pouvons monter que 1 ou 2 marches à chaque tour, lorsque nous nous tenons sur le ième escalier, nous ne pouvions monter que sur les marches i-1 ou i-2 au tour précédent. En d’autres termes, nous ne pouvons passer que du i-1ème ou du i-2ème niveau au i-ème niveau.

De là, nous pouvons tirer une conclusion importante : le nombre de plans qui ont grimpé au niveau i-1 plus le nombre de plans qui ont grimpé au niveau i-2 est égal au nombre de plans qui ont grimpé au niveau i. -ième niveau. La formule est la suivante :

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

Cela signifie qu'il existe une relation récursive dans le problème de l'escalade du bâtiment et que le problème d'origine peut être résolu en construisant les solutions des sous-problèmes.

Exemple de code Dfs : (recherche)


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

Arbre récursif généré par une récursion violente：

Pour résoudre le problème de duplication mentionné ci-dessus dans l'arbre récursif, le procédé de recherche de mémoire peut être utilisé pour supprimer un grand nombre de sous-arbres identiques qui sont construits de manière répétée, améliorant ainsi l'efficacité du calcul. (sous-problèmes qui se chevauchent）

Recherche mémorisée :

Pour calculer tous les sous-problèmes qui se chevauchent une seule fois, vous devez déclarer un tableau nem pour enregistrer la solution de chaque sous-problème et élaguer les sous-problèmes qui se chevauchent pendant le processus de recherche.

Lorsque dp[i] est calculé pour la première fois, il est enregistré dans nem[i] pour une utilisation ultérieure.
Lorsque dp[i] est calculé à nouveau, le résultat est obtenu directement dans nem[i] pour éviter des calculs répétés de sous-problèmes.

Exemple de code :


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

Après mémorisation, tous les sous-problèmes qui se chevauchent ne sont calculés qu'une seule fois et la complexité temporelle est optimisée à O(n).

Programmation dynamique:

La recherche mémorisée est une méthode "de haut en bas". Nous partons du problème d'origine (nœud racine) et décomposons de manière récursive les sous-problèmes plus importants en sous-problèmes plus petits jusqu'à ce que nous résolvions le plus petit sous-problème connu (nœud feuille). . Ensuite, les solutions aux sous-problèmes sont collectées couche par couche grâce à un retour en arrière pour construire une solution au problème d'origine.

En revanche, la programmation dynamique est une approche « de bas en haut » : en commençant par une solution au plus petit sous-problème et en construisant de manière itérative des solutions aux sous-problèmes plus importants jusqu'à ce qu'une solution au problème d'origine soit obtenue.

Étant donné que la programmation dynamique n'inclut pas de processus de retour en arrière, elle doit uniquement être implémentée en utilisant une itération de boucle sans utiliser de récursion.

Exemple de code : (programmation dynamique, en commençant par le plus petit sous-problème)


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

Processus d'exécution (programmation dynamique) :

Analyse : (programmation dynamique)

Semblable à l'algorithme de backtracking, la programmation dynamique utilise également la notion d'« état » pour représenter une étape spécifique de résolution de problème. Chaque état correspond à un sous-problème et à la solution optimale locale correspondante. Exemple : L'état du problème de montée d'escalier est défini comme l'ordre i de l'escalier actuel.

Sur la base de ce qui précède, nous pouvons résumer les termes courants pour les termes dynamiques :

Le tableau dp est appelé {dp table}, dp[i] représente la solution au sous-problème correspondant à l'état i
L'état correspondant au sous-problème minimum (le premier et le deuxième escalier) est appelé état initial
La formule récursive dp[i] = dp[i-1] + dp[i-2] est appelée l'équation d'état

Optimisation de l'espace :

dp[i] n'est lié qu'à dp[i-1] et dp[i-2]

Au lieu d'utiliser un tableau pour stocker les solutions à tous les sous-problèmes, seules deux variables sont nécessaires pour faire défiler vers l'avant.

Exemple de code :


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

L'espace occupé par le tableau dp est omis et la complexité spatiale est réduite de O(n) à O(1)

Dans les problèmes de programmation dynamique, l'état actuel n'est lié qu'à un nombre limité d'états précédents. Pour le moment, nous ne pouvons conserver que les états nécessaires et économiser de l'espace mémoire grâce à la « réduction de dimensionnalité ». . Cette technique d'optimisation de l'espace est appelée « variables glissantes » ou « tableaux roulants ».

Partage de technologie