La programmation dynamique est une technique puissante pour résoudre des problèmes en décomposant une tâche complexe en sous-problèmes plus simples. Cet article explorera son application à deux défis classiques impliquant les palindromes : le comptage de sous-chaînes palindromiques et la détermniation du nombre minimal de coupes pour partitionner une chaîne en palindromes.

Comptage de Sous-chaînes Palindromiques

Énoncé du Problème

Étant donné une chaîne de caractères s, l'objectif est de compter le nombre total de sous-chaînes qui sont des palindromes. Une sous-chaîne est définie par une séquence contiguë de caractères. Deux sous-chaînes sont considérées distinctes si elles commencent ou se terminent à des positions différentes, même si elles sont composées des mêmes caractères.

Exemple 1 :

<strong>Entrée :</strong> s = "abc"
<strong>Sortie :</strong> 3
<strong>Explication :</strong> Les trois sous-chaînes palindromiques sont : "a", "b", "c".

Exemple 2 :

<strong>Entrée :</strong> s = "aaa"
<strong>Sortie :</strong> 6
<strong>Explication :</strong> Les six sous-chaînes palindromiques sont : "a", "a", "a", "aa", "aa", "aaa".

Contraintes :

• 1 <= s.length <= 1000
• s est composée uniquement de lettres minuscules anglaises.

Signature de la Fonction

class Solution {
public:
    int countSubstrings(string s) {
        // Implémentation ici
    }
};

Approche de Résolution par Programmation Dynamique

Pour déterminer efficacement si une sous-chaîne est un palindrome, nous utilisons une table de programmation dynamique. Soit est_pal[i][j] un booléen qui indique si la sous-chaîne s[i...j] est un palindrome.

Définition de l'état :
est_pal[i][j] est vrai si s[i...j] est un palindrome, faux sinon.

Relation de récurrence :

1. Si s[i] != s[j], alors est_pal[i][j] est false.
2. Si s[i] == s[j] :
   • Si la sous-chaîne s[i...j] a une longueur de 1 ou 2 caractères (c'est-à-dire j - i < 2), elle est nécessairement un palindrome. Ainsi, est_pal[i][j] = true.
   • Si la sous-chaîne a plus de 2 caractères, elle est un palindrome si et seulement si la sous-chaîne interne s[i+1...j-1] est également un palindrome. Donc, est_pal[i][j] = est_pal[i+1][j-1].

Ordre de calcul :
Pour garantir que est_pal[i+1][j-1] est déjà calculé lorsque nous en avons besoin, nous devons parocurir le tableau dans un ordre spécifique. Il est judicieux d'itérer i de la fin de la chaîne vers le début (de n-1 à 0) et j du début vers la fin (de i à n-1).

Initialisation :
La table est_pal est généralement initialisée à false. Les cas de base (longueur 1 ou 2) sont gérés directement dans la relation de récurrence.

Comptage du résultat :
Chaque fois que est_pal[i][j] est calculé comme true, nous incrémentons un compteur global. Ce compteur sera le résultat final.

Implémentation

class Solution {
public:
    int countSubstrings(string s) {
        int longueur_chaine = s.length();
        vector<vector>> est_pal(longueur_chaine, vector<bool>(longueur_chaine, false));
        int total_palindromes = 0;

        // Parcourir la chaîne en ordre inverse pour l'indice de début (i)
        for (int i = longueur_chaine - 1; i >= 0; --i) {
            // Parcourir la chaîne pour l'indice de fin (j)
            for (int j = i; j < longueur_chaine; ++j) {
                if (s[i] == s[j]) { // Si les caractères aux extrémités correspondent
                    if (j - i < 2) { // Cas de base: sous-chaîne de 1 ou 2 caractères
                        est_pal[i][j] = true;
                    } else { // Cas récursif: dépend de la sous-chaîne interne
                        est_pal[i][j] = est_pal[i + 1][j - 1];
                    }
                }
                
                // Si est_pal[i][j] est vrai, cela signifie que s[i...j] est un palindrome
                if (est_pal[i][j]) {
                    total_palindromes++;
                }
            }
        }
        return total_palindromes;
    }
};
</bool></vector>

Partitionnement d'une chaîne en palindromes avec un minimum de coupes

Énoncé du Problème

Donnée une chaîne s, nous devons la diviser en un ensemble de sous-chaînes telles que chaque sous-chaîne résultante soit un palindrome. Le défi est de trouver le nombre minimal de coupes nécessaires pour réaliser ce partitionnement.

Exemple 1 :

<strong>Entrée :</strong> s = "aab"
<strong>Sortie :</strong> 1
<strong>Explication :</strong> La chaîne peut être divisée en ["aa", "b"] avec une seule coupe.

Exemple 2 :

<strong>Entrée :</strong> s = "a"
<strong>Sortie :</strong> 0

Exemple 3 :

<strong>Entrée :</strong> s = "ab"
<strong>Sortie :</strong> 1

Contraintes :

• 1 <= s.length <= 2000
• s est composée uniquement de lettres minuscules anglaises.

Signature de la Fonction

class Solution {
public:
    int minCut(string s) {
        // Implémentation ici
    }
};

Stratégie de Résolution par Programmation Dynamique

Ce problème nécessite deux étapes principales de programmation dynamique. Premièrement, nous précalculons toutes les sous-chaînes palindromiques possibles. Deuxièmement, nous utilisons ces informations pour calculer le nombre minimal de coupes.

1. Pré-calcul des palindromes :
Nous utilisons la même technique que pour le problème précédent. Une table est_segment_palindrome[i][j] indiquera si la sous-chaîne s[i...j] est un palindrome. Cette étape est essentielle car elle permet de vérifier en temps constant si une sous-chaîne est un palindrome lors du calcul des coupes minimales.

2. Calcul des coupes minimales :
Soit coupes_min_prefixe[k] le nombre minimal de coupes nécessaires pour partitionner la sous-chaîne s[0...k] en palindromes.

Définition de l'état :
coupes_min_prefixe[k] = nombre minimum de coupes pour que s[0...k] soit entièrement composée de palindromes.

Relation de récurrence :
Pour chaque indice k allant de 0 à n-1 (où n est la longueur de la chaîne) :

• Si la sous-chaîne s[0...k] est déjà un palindrome (c'est-à-dire est_segment_palindrome[0][k] est vrai), alors aucune coupe n'est nécessaire pour ce préfixe : coupes_min_prefixe[k] = 0.
• Sinon, nous devons trouver la meilleure coupe. Pour cela, nous itérons sur toutes les positions j de 0 à k-1. Si la sous-chaîne s[j+1...k] est un palindrome (c'est-à-dire est_segment_palindrome[j+1][k] est vrai), alors nous pouvons envisager de faire une coupe après l'indice j. Le coût total serait alors coupes_min_prefixe[j] + 1 (les coupes pour s[0...j] plus une coupe pour séparer s[j+1...k]). Nous prenons le minimum de toutes ces possibilités : coupes_min_prefixe[k] = min(coupes_min_prefixe[k], coupes_min_prefixe[j] + 1).

Initialisation :
coupes_min_prefixe[k] est initialisé avec une valeur maximale (par exemple, k, car dans le pire des cas, chaque caractère peut être coupé individuellement) pour assurer que la fonction min trouve correctement la valeur la plus petite.

Ordre de calcul :
Les valeurs coupes_min_prefixe[k] sont calculées de k=0 à n-1, car le calcul de coupes_min_prefixe[k] dépend des valeurs précédentes coupes_min_prefixe[j] où j < k.

Résultat :
La réponse finale est coupes_min_prefixe[n-1], qui représente le nombre minimal de coupes pour toute la chaîne s.

Implémentation

#include <string>
#include <vector>
#include <algorithm> // Pour std::min
#include <limits>    // Pour std::numeric_limits

class Solution {
public:
    int minCut(string s) {
        int n = s.length();

        // Étape 1: Pré-calculer toutes les sous-chaînes palindromiques
        vector<vector>> est_segment_palindrome(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (j - i < 2) {
                        est_segment_palindrome[i][j] = true;
                    } else {
                        est_segment_palindrome[i][j] = est_segment_palindrome[i + 1][j - 1];
                    }
                }
            }
        }

        // Étape 2: Calculer le nombre minimal de coupes
        vector<int> coupes_min_prefixe(n);

        for (int i = 0; i < n; ++i) {
            if (est_segment_palindrome[0][i]) {
                // Si s[0...i] est un palindrome, aucune coupe n'est nécessaire pour ce préfixe
                coupes_min_prefixe[i] = 0;
            } else {
                // Initialiser avec le pire des cas (chaque caractère est coupé)
                coupes_min_prefixe[i] = i; 
                // Rechercher le point de coupe optimal
                for (int j = 0; j < i; ++j) {
                    // Si s[j+1...i] est un palindrome
                    if (est_segment_palindrome[j + 1][i]) {
                        // Le nombre de coupes serait les coupes pour s[0...j] plus 1 (pour la coupe à j)
                        coupes_min_prefixe[i] = min(coupes_min_prefixe[i], coupes_min_prefixe[j] + 1);
                    }
                }
            }
        }
        
        return coupes_min_prefixe[n - 1];
    }
};
</int></bool></vector></limits></algorithm></vector></string>