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]