Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.
Si le problème se résume au fait qu'il est nécessaire de diviser le tableau en sous-segments non sécants (une séquence d'éléments consécutifs) de manière optimale (ou de compter le nombre de divisions appropriées), alors cela vaut la peine d'essayer de le résoudre en utilisant la programmation dynamique.
Un exemple de schéma de solution est le suivant :
dp[i] - réponse pour les premiers i éléments
Compter dp[i] : puisque nous ne considérons que les i premiers éléments, le i-ème élément sera le dernier, ce qui signifie que cet élément sera dans le dernier sous-segment et, en même temps, le plus à droite. Par conséquent, nous pouvons itérer sur la limite gauche du dernier sous-segment j. Dans le processus d'énumération, nous calculerons la valeur de ce sous-segment, et si elle est correcte, nous recalculerons dp[i] à dp[j - 1] et la valeur du sous-segment [j;i].
Considérez le problème simple suivant : étant donné un tableau d'entiers, vous devez le diviser en un nombre minimum de sous-segments non croisés afin que chaque nombre soit inclus dans un sous-segment et que chaque sous-segment contienne les mêmes nombres. Par exemple, pour un tableau 1 2 2 3 3 3 2 1 1, la partition optimale ressemble à ceci : [1] [2 2] [3 3 3] [2] [1 1]. Cette tâche est facilement résolue en passant simplement par le tableau (nous mettons tous les mêmes éléments consécutifs dans un sous-segment), mais nous allons le résoudre en utilisant la programmation dynamique pour un exemple.
international ;
cin>> n;
// remplit le tableau avec 1-index
vecteurarr(n + 1);
pour (int je = 1; je <= n; je++)
cin>> arr[i] ;
// définit initialement +oo sur les valeurs dp
vecteur dp(n + 1, 1000000000);
// un tableau de longueur zéro n'a pas besoin d'être divisé, donc la réponse est 0
dp[0] = 0 ;
// compte la réponse pour dp[i] en i croissant
pour (int je = 1; je <= n; je++) {
// actuellement arr[i] est le dernier élément, donc ce sera le nombre le plus à droite dans le dernier sous-segment
// boucle à travers toutes les options pour savoir où ce dernier sous-segment a commencé
pour (int j = je; j > 0; j--) {
si (arr[j] != arr[i]) {
// si vous rencontrez un élément qui n'est pas égal au dernier, alors le sous-segment contiendra des nombres différents, et cela ne correspond pas à la condition
// inutile de continuer, car en décalant la bordure gauche vers la gauche, cet élément ne disparaîtra pas, donc on casse
casser;
}
// imaginez que le dernier sous-segment était [j;i]
// vous devez donc prendre la partition optimale des premiers éléments j-1 et ajouter 1 (le sous-segment [j; i] lui-même)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n] ;
Si les éléments ne peuvent appartenir à aucun des sous-segments, il vous suffit de considérer l'option appropriée, car dp[i] = dp[i - 1]
|
S'il est nécessaire de diviser le tableau en exactement k sous-segments, le deuxième paramètre est simplement ajouté dans la programmation dynamique - le nombre de segments à diviser.
Autrement dit, nous allons maintenant considérer le dp suivant :
dp[i][j] est la réponse pour les i premiers éléments, si nous les divisons en exactement j segments.
Faites attention aux états invalides.
Le recalcul de la dynamique est le même, mais en tenant compte du second paramètre. Autrement dit, en comptant dp[i][k] et en triant par la bordure gauche du dernier sous-segment j, nous recalculons dp[i][k] à dp[j - 1][k - 1] et la valeur du segment [j;i].
|
Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.
S'il y a un ensemble d'écarts situés sur un axe (généralement l'axe du temps ou les indices d'un tableau) et que vous devez en choisir certains de manière optimale afin que les écarts sélectionnés ne se croisent pas, alors vous devriez essayer d'utiliser la programmation dynamique .
Schéma de solution approximatif :
Initialement, nous trions les espaces disponibles par la bordure droite. Commençons la dynamique suivante : dp[i] - la réponse pour les premiers intervalles i.
Nous allons recalculer comme suit : d'abord, considérons la situation où cet intervalle ne sera pas utilisé, puis simplement dp[i] = dp[i-1]. Notez que cela garantit que les valeurs de dp[i] ne diminuent pas à mesure que i grandit. Et c'est logique, parce que. en ajoutant un nouvel écart, on ne peut pas aggraver la réponse globale : soit on ignore simplement le nouvel écart, soit on construit une variante plus rentable en l'utilisant. Maintenant, si nous voulons utiliser le i-ième espace, nous pouvons utiliser les espaces dont les bords droits sont inférieurs au bord gauche de l'espace actuel, car nous devons choisir un ensemble d'espaces qui ne se chevauchent pas. Pour ce faire, nous avons d'abord trié les espaces par la bordure droite, de sorte que nous puissions maintenant trouver efficacement la position requise. Cela peut être fait analytiquement, si possible, mais dans le cas général, il est possible de trouver un écart avec un binsearch dont le bord droit est inférieur au bord gauche de celui en cours et, en même temps, le maximum possible un. Nous voulons maximiser la bonne frontière pour des raisons gourmandes, parce que à mesure que je grandis, la réponse ne peut qu'augmenter. En conséquence, nous trouvons la position requise p et recalculons dp[i] à dp[p] et le i-ième intervalle.
|