La programmation dynamique offre des solutions efficaces pour résoudre des problèmes d'optimisation combinatoire. Un classique est de déterminer la plus longue sous-séquence strictement croissante (LIS) dans une suite donnée. Cette section explore plusieurs approches algorithmiques, de la méthode naïve en O(n²) à l'optimisation en O(n log n), ainsi que leurs variantes.
Solution de base en O(n²)
Soit une séquence a de taille n. On définit f[i] comme la longueur de la LIS se terminant à l'index i. La relation de récurrence est :
f[i] = max(f[j] + 1) pour tout j < i avec a[j] < a[i]
f[i] = 1 si aucun j ne satisfait la condition
La longueur du résultat est le maximum de tous les f[i].
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int taille;
std::cin >> taille;
std::vector<int> donnees(taille);
for (int i = 0; i < taille; ++i) {
std::cin >> donnees[i];
}
std::vector<int> longueur(taille, 1);
int resultat = 1;
for (int i = 1; i < taille; ++i) {
for (int j = 0; j < i; ++j) {
if (donnees[j] < donnees[i]) {
longueur[i] = std::max(longueur[i], longueur[j] + 1);
}
}
resultat = std::max(resultat, longueur[i]);
}
std::cout << resultat << std::endl;
return 0;
}
Optimisation en O(n log n)
On maintient un tableau queue où queue[k] stocke la plus petite valeur posible pouvant terminer une LIS de lnogueur k+1. Ce tableau est toujours trié.
Pour chaque nouvel élément x : - Si x est supérieur à tous les éléments dans queue, on l'ajoute à la fin (allongeant la LIS). - Sinon, on trouve la première position dans queue dont la valeur est ≥ x et on la remplace par x. Cela garantit que queue reste une séquence potentiellement plus favorable pour de futures extensions.
L'algorithme utilise la recherche binaire pour une complexité en O(n log n).
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int taille;
std::cin >> taille;
std::vector<int> donnees(taille);
for (int i = 0; i < taille; ++i) {
std::cin >> donnees[i];
}
std::vector<int> queue;
queue.reserve(taille);
for (int x : donnees) {
auto it = std::lower_bound(queue.begin(), queue.end(), x);
if (it == queue.end()) {
queue.push_back(x);
} else {
*it = x;
}
}
std::cout << queue.size() << std::endl;
return 0;
}
Reconstruction de la séquence
Pour afficher une LIS (pas seulement sa longueur), on peut associer à chaque index i la longueur de la LIS se terminant en i et effectuer une rétrospection depuis la fin.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int taille;
std::cin >> taille;
std::vector<int> donnees(taille);
for (int i = 0; i < taille; ++i) {
std::cin >> donnees[i];
}
std::vector<int> queue;
std::vector<int> longueur_finale(taille);
queue.reserve(taille);
for (int i = 0; i < taille; ++i) {
int x = donnees[i];
auto pos = std::lower_bound(queue.begin(), queue.end(), x);
if (pos == queue.end()) {
queue.push_back(x);
} else {
*pos = x;
}
longueur_finale[i] = pos - queue.begin() + 1;
}
int longueur_max = queue.size();
std::cout << "Longueur de la LIS : " << longueur_max << std::endl;
std::vector<int> sous_sequence;
int cible = longueur_max;
for (int i = taille - 1; i >= 0 && cible > 0; --i) {
if (longueur_finale[i] == cible) {
sous_sequence.push_back(donnees[i]);
--cible;
}
}
std::reverse(sous_sequence.begin(), sous_sequence.end());
std::cout << "La plus longue sous-séquence croissante : ";
for (int val : sous_sequence) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
Variatne : Somme maximale d'une sous-séquence croissante
On cherche la sous-séquence croissante dont la somme des éléments est maximale. La définition de f[i] change : elle représente la somme maximale d'une telle sous-séquence se terminant en i.
f[i] = a[i] + max(f[j]) pour tout j < i avec a[j] < a[i]
f[i] = a[i] si aucun j ne satisfait la condition
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int taille;
std::cin >> taille;
std::vector<int> donnees(taille);
for (int i = 0; i < taille; ++i) {
std::cin >> donnees[i];
}
std::vector<long long> somme_max(taille);
long long resultat_global = 0;
for (int i = 0; i < taille; ++i) {
somme_max[i] = donnees[i];
for (int j = 0; j < i; ++j) {
if (donnees[j] < donnees[i]) {
somme_max[i] = std::max(somme_max[i], somme_max[j] + donnees[i]);
}
}
resultat_global = std::max(resultat_global, somme_max[i]);
}
std::cout << resultat_global << std::endl;
return 0;
}
Plus longue sous-séquence décroissante
Le problème duale peut être résolu en inversant la comparaison ou en appliquant l'algorithme de la LIS sur la séquence inversée.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int taille;
std::cin >> taille;
std::vector<int> donnees(taille);
for (int i = 0; i < taille; ++i) {
std::cin >> donnees[i];
}
std::vector<int> queue;
queue.reserve(taille);
for (int x : donnees) {
auto it = std::upper_bound(queue.begin(), queue.end(), x, std::greater<int>());
if (it == queue.end()) {
queue.push_back(x);
} else {
*it = x;
}
}
std::cout << queue.size() << std::endl;
return 0;
}
Application : Route en montagne et en descente (Problème de la chorale)
Pour une séquence donnée, trouver la longueur maximale d'une sous-séquence qui d'abord croît puis décroît (ou une variante similaire). On combine les calculs de LIS et de LDS (Longest Decreasing Subsequence).
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
std::vector<int> lis_finissant(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (a[j] < a[i]) {
lis_finissant[i] = std::max(lis_finissant[i], lis_finissant[j] + 1);
}
}
}
std::vector<int> lds_debutant(n, 1);
for (int i = n - 2; i >= 0; --i) {
for (int j = n - 1; j > i; --j) {
if (a[j] < a[i]) {
lds_debutant[i] = std::max(lds_debutant[i], lds_debutant[j] + 1);
}
}
}
int longueur_route = 0;
for (int i = 0; i < n; ++i) {
longueur_route = std::max(longueur_route, lis_finissant[i] + lds_debutant[i] - 1);
}
// Pour la "chorale", le nombre minimum à retirer serait n - longueur_route
std::cout << "Longueur maximale de la montée-descente : " << longueur_route << std::endl;
std::cout << "Personnes à retirer pour la chorale : " << n - longueur_route << std::endl;
return 0;
}
Plus longue sous-séquence commune croissante (LCIS)
Étant donné deux séquences A et B, trouver la plus longue sous-séquence qui est à la fois croissante et présente dans les deux séquences. Une solution en O(nm) utilise une programmation dynamique à deux dimensions.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, m;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) std::cin >> a[i];
std::cin >> m;
std::vector<int> b(m + 1);
for (int j = 1; j <= m; ++j) std::cin >> b[j];
// dp[i][j] : longueur du LCIS se terminant avec a[i] et b[j]
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) {
int meilleur = 0;
for (int j = 1; j <= m; ++j) {
dp[i][j] = dp[i - 1][j]; // Hériter de la valeur précédente sur A
if (a[i] == b[j]) {
// On peut terminer le LCIS ici
dp[i][j] = std::max(dp[i][j], meilleur + 1);
}
if (a[i] > b[j]) {
// Mettre à jour la meilleure longueur pour une valeur inférieure
meilleur = std::max(meilleur, dp[i][j]);
}
}
}
int resultat = 0;
for (int j = 1; j <= m; ++j) {
resultat = std::max(resultat, dp[n][j]);
}
std::cout << resultat << std::endl;
return 0;
}
Les techniques présentées illustrent la flexibilité de la programmation dynamique et de la recherche binaire pour résoudre des problèmes d'optimisation sur les séquences.