1. Concepts Fondamentaux et Distinction avec le Diviser pour Régner

La programmation dynamique (PD) est une méthode algorithmique conçue pour résoudre des problèmes d'optimisation. Bien qu'elle partage une similarité superficielle avec l'approche du diviser pour régner — toutes deux décomposant un problème complexe en sous-problèmes plus simples jusqu'à atteindre des cas de base — leurs mécanismes sous-jacents diffèrent radicalement sur plusieurs aspects cruciaux :

• Chevauchement des sous-problèmes : En PD, les sous-problèmes partagent souvent des sous-sous-problèmes communs. À l'inverse, le diviser pour régner génère généralement des sous-problèmes totalement indépendants.
• Mémorisation des résultats : La PD stocke les solutions intermédiaires dans une structure de données (souvent un tableau) pour éviter de recalculer plusieurs fois le même sous-problème, réduisant ainsi drastiquement la redondance.
• Conditions d'application : L'utilisation de la PD exige que le problème possède une sous-structure optimale et des sous-problèmes chevauchants. Le diviser pour régner n'impose pas ces restrictions strictes.
• Complexité temporelle : Une approche naïve par diviser pour régner sur des problèmes à chevauchement peut mener à une complexité exponentielle $O(2^n)$. La PD ramène cette complexité à un niveau polynomial, typiquement $O(n^2)$ ou $O(n \cdot C)$.

Pour illustrer le chevauchement, considérons l'arbre de récursion du problème du sac à dos. Sans mémorisation, l'évaluation de la capacité restante pour un sous-ensemble d'objets sera recalculée de multiples fois via des chemins de décision différents. La PD élimine cette redondance.

La résolution d'un problème via la programmation dynamique suit généralement quatre étapes formelles :

1. Caractériser la structure d'une solution optimale.

2. Définir récursivement la valeur d'une solution optimale (équation de récurrence).

3. Calculer la valeur de la solution optimale (appproche ascendante ou descendante).

4. Construire la solution optimale elle-même à partir des informations calculées.

5. Anatomie de la Programmation Dynamique

La première étape consiste à valider la présence d'une sous-structure optimale. Un problème possède cette propriété si la solution optimale globale contient en son sein les solutions optimales de ses sous-problèmes. Mathématiquement, la valeur optimale est le résultat d'un choix local immédiat combiné à la valeur optimale du sous-problème résultant.

Il est crucial de noter que certains problèmes violent cette propriété. Par exemple, trouver le plus long chemin simple dans un graphe orienté non pondéré ne possède pas de sous-structure optimale. Le calcul du chemin le plus long entre deux nœuds intermédiaires peut verrouiller l'utilisation de certains sommets, empêchant leur réutilsiation dans d'autres segments du chemin, créant ainsi une interférence entre les sous-problèmes.

La seconde propriété requise est le chevauchement des sous-problèmes. L'espace des sous-problèmes doit être suffisamment petit pour que l'algorithme récursif résolve de manière répétée les mêmes problèmes. C'est cette redondance qui justifie l'utilisation d'une table de mémorisation.

L'équation de récurrence (ou équation de transition d'état) est le cœur de l'algorithme. Elle exprime la solution d'un état en fonction des solutions d'états précédents. Elle doit également inclure les conditions aux limites (cas de base), qui représentent les problèmes atomiques dont la solution est triviale.

Lors de l'implémentation, si l'on choisit l'approche ascendante (bottom-up), l'ordre de remplissage de la table est critique. Il faut s'assurer que lorsqu'un état est calculé, tous les états dont il dépend ont déjà été évalués et stockés.

3. Étude de Cas : Le Problème du Sac à Dos 0-1

Pour concrétiser ces concepts, analysons le problème classique du sac à dos 0-1. Étant donné une capacité maximale $C$, un ensemble de $N$ objets, chaque objet ayant un poids $poids[i]$ et une valeur $valeur[i]$, l'objectif est de maximiser la valeur totale sans dépasser la capacité $C$. Chaque objet ne peut être pris qu'en entier ou laissé (0 ou 1).

Définition de l'état : Soit $dp[i][c]$ la valeur maximale pouvant être obtenue en utilisant un sous-ensemble des $i$ premiers objets avec une capacité restante $c$.

Équation de transition : Pour chaque objet $i$, deux choix s'offrent à nous :

• Ne pas inclure l'objet $i$ : La valeur maximale reste celle obtenue avec les $i-1$ premiers objets pour la même capacité. $dp[i][c] = dp[i-1][c]$
• Inclure l'objet $i$ (si $poids[i] \le c$) : La valeur est celle de l'objet actuel plus la valeur maximale obtenue avec les $i-1$ premiers objets et la capacité réduite. $dp[i][c] = valeur[i] + dp[i-1][c - poids[i]]$

La valeur de $dp[i][c]$ sera le maximum de ces deux options.

Conditions aux limites : $dp[0][c] = 0$ (aucun objet disponible) et $dp[i][0] = 0$ (capacité nulle).

4. Implémentations Algorithmiques

Voici trois implémentations en Java, allant de l'approche récursive avec mémoïsation à l'optimisation spatiale avancée.

Approche Descendante avec Mémoïsation (Top-Down)

Cette approche utilise la récursivité tout en cachant les résultats dans un tableau pour éviter les recalculs.

import java.util.Arrays;

public class KnapsackTopDown {
    
    public static int solve(int capacity, int[] weights, int[] values) {
        int itemCount = values.length;
        int[][] memo = new int[itemCount + 1][capacity + 1];
        
        // Initialisation avec -1 pour indiquer les états non calculés
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        
        return compute(capacity, weights, values, itemCount, memo);
    }

    private static int compute(int remCap, int[] wt, int[] val, int idx, int[][] memo) {
        // Conditions aux limites
        if (idx == 0 || remCap == 0) {
            return 0;
        }
        
        // Retourner le résultat s'il est déjà en cache
        if (memo[idx][remCap] != -1) {
            return memo[idx][remCap];
        }

        // Si l'objet actuel est trop lourd, on ne peut que l'exclure
        if (wt[idx - 1] > remCap) {
            return memo[idx][remCap] = compute(remCap, wt, val, idx - 1, memo);
        }

        // Choix : inclure ou exclure l'objet
        int includeItem = val[idx - 1] + compute(remCap - wt[idx - 1], wt, val, idx - 1, memo);
        int excludeItem = compute(remCap, wt, val, idx - 1, memo);
        
        return memo[idx][remCap] = Math.max(includeItem, excludeItem);
    }
}

Approche Ascendante avec Tableau 2D et Reconstruction (Bottom-Up)

Cette méthode itérative remplit le tableau de manière systématique. Un tableau booléen supplémentaire est utilisé pour tracer les choix et reconstruire la solution optimale.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class KnapsackBottomUp2D {

    public static class Result {
        public int maxValue;
        public List<Integer> selectedItems;

        public Result(int maxValue, List<Integer> selectedItems) {
            this.maxValue = maxValue;
            this.selectedItems = selectedItems;
        }
    }

    public static Result solveWithReconstruction(int maxCap, int[] wt, int[] val) {
        int n = val.length;
        int[][] dp = new int[n + 1][maxCap + 1];
        boolean[][] keep = new boolean[n + 1][maxCap + 1];

        // Remplissage de la table DP
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= maxCap; c++) {
                if (wt[i - 1] <= c && val[i - 1] + dp[i - 1][c - wt[i - 1]] > dp[i - 1][c]) {
                    dp[i][c] = val[i - 1] + dp[i - 1][c - wt[i - 1]];
                    keep[i][c] = true;
                } else {
                    dp[i][c] = dp[i - 1][c];
                }
            }
        }

        // Reconstruction de la solution
        List<Integer> items = new ArrayList<>();
        int currentCap = maxCap;
        for (int i = n; i > 0; i--) {
            if (keep[i][currentCap]) {
                items.add(i); // Index basé sur 1 pour l'objet
                currentCap -= wt[i - 1];
            }
        }
        Collections.reverse(items);
        
        return new Result(dp[n][maxCap], items);
    }
}

Optimisation Spatiale avec Tableau 1D

En analysant l'équation de transition $dp[i][c] = \max(dp[i-1][c], dp[i-1][c - wt[i-1]] + val[i-1])$, on constate que l'état actuel ne dépend que de la ligne précédente ($i-1$). Nous pouvons donc réduire l'espace mémoire de $O(N \cdot C)$ à $O(C)$ en utilisant un tableau unidimensionnel. L'itération sur la capacité doit se faire en ordre décroissant pour éviter d'écraser les valeurs de la ligne précédente dont nous avons encore besoin.

public class KnapsackSpaceOptimized {

    public static int solve(int maxCap, int[] weights, int[] values) {
        int n = values.length;
        int[] dp = new int[maxCap + 1];

        for (int i = 1; i <= n; i++) {
            // Parcours décroissant pour préserver les états de l'itération précédente
            for (int c = maxCap; c >= weights[i - 1]; c--) {
                int exclude = dp[c];
                int include = dp[c - weights[i - 1]] + values[i - 1];
                dp[c] = Math.max(exclude, include);
            }
        }

        return dp[maxCap];
    }
}