Algorithme de programmation dynamique en C++ et ses compétences applicatives

La programmation dynamique (DP) est un algorithme efficace utilisé pour résoudre certains problèmes avec des sous-problèmes qui se chevauchent et des propriétés de sous-structure optimales. Il existe certaines techniques pour améliorer l'efficacité lors de la mise en œuvre d'algorithmes de programmation dynamique en langage C++. Cet article présentera l'algorithme de programmation dynamique et ses techniques d'application en C++.

L'idée principale de l'algorithme de programmation dynamique est de décomposer le problème en une série de sous-problèmes, et lors de la résolution de chaque sous-problème, de conserver un état et d'utiliser cet état pour éviter les calculs répétés. L'algorithme de programmation dynamique peut résoudre certains problèmes coûteux en termes de calcul, car il suffit de calculer chaque sous-problème une fois au lieu de chaque fois.

1. Trois éléments de la programmation dynamique

L'algorithme de programmation dynamique doit répondre à trois éléments :

(1) Sous-structure optimale : La solution optimale d'un problème contient la solution optimale de ses sous-problèmes.

(2) Aucune séquelle : Tous les états du processus sont uniquement liés à l'état actuel et n'ont rien à voir avec l'état précédent.

(3) Sous-problèmes qui se chevauchent : plusieurs sous-problèmes se chevauchent pour éviter des calculs répétés.

2. Classification de base de la programmation dynamique

Il existe deux classifications de base de la programmation dynamique : l'une est la programmation dynamique basée sur l'état et l'autre est la programmation dynamique basée sur les décisions. La programmation dynamique basée sur l'état consiste à enregistrer les solutions de chaque sous-problème pendant le calcul, puis à calculer la solution au problème plus vaste en fonction des valeurs de ces solutions. L'état est généralement enregistré à l'aide d'une structure de données, telle qu'un tableau. La programmation dynamique basée sur la décision fait référence à la détermination de la solution optimale au problème plus vaste en fonction de la solution optimale de chaque sous-problème lors du calcul. Cette méthode est souvent utilisée pour résoudre des problèmes d'optimisation ou lors du calcul de la valeur minimale.

3. Compétences d'application de la programmation dynamique

Lors de la mise en œuvre d'algorithmes de programmation dynamique en C++, certaines compétences d'application peuvent améliorer l'efficacité. Ces techniques incluent :

(1) Utiliser des constantes au lieu d'indices de tableau : dans certains problèmes de programmation dynamique, plusieurs accès au tableau sont requis. À ce stade, vous pouvez remplacer l’indice du tableau par une constante, ce qui peut accélérer l’accès. Par exemple :

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

Vous pouvez utiliser la variable k pour remplacer l'indice du tableau dp :

for(int k=2;k<=n+m;k++){
    for(int i=1;i<=n;i++){
        int j = k-i;
        if(j<1 || j>m) continue;
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

(2) Optimiser le tableau : Dans certains problèmes de programmation dynamique, la taille du tableau est très grande, ce qui peut entraîner des limitations de mémoire . À ce stade, vous pouvez utiliser un tableau déroulant ou la première dimension d'un tableau bidimensionnel pour enregistrer les résultats intermédiaires. Par exemple :

int dp[N][M];
for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

peut être optimisé pour :

int dp[2][M];
for(int i=0;i<N;i++){
    int cur = i%2, pre = (i+1)%2;
    for(int j=0;j<M;j++){
        dp[cur][j] = max(dp[pre][j],dp[cur][j-1])+1;
    }
}

(3) Économie d'espace : dans certains problèmes de programmation dynamique, seuls les états les plus récents doivent être enregistrés au lieu du tableau entier. À l’heure actuelle, vous pouvez utiliser un tableau défilant pour enregistrer uniquement les états les plus récents.

(4) Évitez les calculs répétés : Dans certains problèmes de programmation dynamique, il peut y avoir des sous-problèmes répétés. À ce stade, vous pouvez utiliser la recherche mémorisée ou la programmation dynamique ascendante pour éviter les calculs répétés.

4. Exemples de programmation dynamique

Voici quelques exemples de problèmes de programmation dynamique :

(1) Séquence de Fibonacci : La séquence de Fibonacci signifie qu'à partir de 0 et 1, chaque nombre est égal aux deux précédents La somme des Nombres. Par exemple, 0, 1, 1, 2, 3, 5, 8, 13, 21.

La formule de récursion est : f[n] = f[n-1] + f[n-2]

En utilisant un algorithme de programmation dynamique, elle peut être réalisée comme suit :

int dp[N];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
    dp[i] = dp[i-1] + dp[i-2];
}

(2) Problème du sac à dos : Le sac à dos le problème signifie qu'il y a N éléments, chaque élément a un poids et une valeur. Etant donné la capacité C d'un sac à dos, trouver la valeur maximale qu'on peut charger sans dépasser la capacité du sac à dos.

En utilisant l'algorithme de programmation dynamique, vous pouvez réaliser ce qui suit :

int dp[N][C];
for(int i=0;i<N;i++){
    for(int j=0;j<C;j++){
        dp[i][j] = 0;
    }
}
for(int i=0;i<N;i++){
    for(int j=0;j<=C;j++){
        if(j>=w[i]){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
        else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

Ce qui précède est une brève introduction à l'algorithme de programmation dynamique et à ses techniques d'application en C++. Pour les problèmes de programmation dynamique complexes, la complexité temporelle et la complexité spatiale doivent également être prises en compte. Par conséquent, lors de la mise en œuvre d’un algorithme de programmation dynamique, il est nécessaire de prendre en compte divers facteurs et de sélectionner une méthode appropriée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!