Approches de programmation dynamique

Suite de Fibonacci - Approche descendante

Le problème de Fibonacci (LeetCode 509) peut être résolu avec deux approches descendantes : la récursion complète et la récursion avec mémorisation.

public int fibonacci(int n) {
    int[] cache = new int[n + 1];
    return calculerFibonacci(cache, n);
}

private int calculerFibonacci(int[] cache, int n) {
    if (n <= 1) {
        return n;
    }
    if (cache[n] != 0) {
        return cache[n];
    }
    cache[n] = calculerFibonacci(cache, n - 1) + calculerFibonacci(cache, n - 2);
    return cache[n];
}

Suite de Fibonacci - Approche asecndante

L'approche ascendante élimine la récursion en construisant la solution progressivement.

public int fibonacciIteratif(int n) {
    if (n <= 1) {
        return n;
    }
    int precedent1 = 0;
    int precedent2 = 1;
    int resultat = 0;
    
    for (int i = 2; i <= n; i++) {
        resultat = precedent1 + precedent2;
        precedent1 = precedent2;
        precedent2 = resultat;
    }
    return resultat;
}

Échange de monnaie - Approche récursive

Le problème d'échange de monnaie (LeetCode 322) consiste à trouver le nombre minimum de pièces pour former un montant donné.

private int[] memoire;

public int nombreMinimumPieces(int[] pieces, int montant) {
    memoire = new int[montant + 1];
    Arrays.fill(memoire, -999);
    return resoudreSousProbleme(pieces, montant);
}

private int resoudreSousProbleme(int[] pieces, int reste) {
    if (reste == 0) return 0;
    if (reste < 0) return -1;
    
    if (memoire[reste] != -999) {
        return memoire[reste];
    }
    
    int minimum = Integer.MAX_VALUE;
    for (int piece : pieces) {
        int sousResultat = resoudreSousProbleme(pieces, reste - piece);
        if (sousResultat == -1) continue;
        minimum = Math.min(minimum, sousResultat + 1);
    }
    
    memoire[reste] = (minimum != Integer.MAX_VALUE) ? minimum : -1;
    return memoire[reste];
}

Échange de monnaie - Programmation dynamique

L'approche itérative construit la solution du plus petit montant vers le montant cible.

public int echangeMonnaieDP(int[] pieces, int montant) {
    int[] dp = new int[montant + 1];
    Arrays.fill(dp, montant + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= montant; i++) {
        for (int piece : pieces) {
            if (i - piece >= 0) {
                dp[i] = Math.min(dp[i], dp[i - piece] + 1);
            }
        }
    }
    
    return dp[montant] <= montant ? dp[montant] : -1;
}