Dernière Poids de Pierre II (LeetCode 1049)

Ce problème consiste à minimiser le poids restant après avoir brisé des pierres. L'approche optimale transforme le problème en recherche d'une pratition équilibrée des pierres.

Stratégie de résolution

1. Calculer la somme totale des poids
2. Définir la cible comme la moitié de cette somme
3. Utiliser un sac à dos pour maximiser le poids sans dépasser la cible
4. Le résultat est la différence entre les deux partitions

class Solution {
public:
    int lastStoneWeightII(vector<int>& rochers) {
        int total = accumulate(rochers.begin(), rochers.end(), 0);
        int demi = total / 2;
        vector<int> sac(demi + 1, 0);
        
        for (int rocher : rochers) {
            for (int p = demi; p >= rocher; p--) {
                sac[p] = max(sac[p], sac[p - rocher] + rocher);
            }
        }
        
        return total - 2 * sac[demi];
    }
};

Objectif de Somme (LeetCode 494)

Compter les façons d'attribuer des signes aux éléments pour atteindre une cible spécifique.

Transformation du problème

Soit S la somme totale et T la cible :

• Partition positive : P = (S + T) / 2
• Si (S + T) est impair, aucune solusion n'existe

Approche dynamique

1. Initialiser dp[0] = 1 (façon vide)
2. Pour chaque nombre, mettre à jour le tableau des possibilités
3. dp[P] donne le nombre de solutions

class Solution {
public:
    int findTargetSumWays(vector<int>& nombres, int cible) {
        int total = accumulate(nombres.begin(), nombres.end(), 0);
        if ((total + cible) % 2 || total + cible < 0) return 0;
        int partition = (total + cible) / 2;
        
        vector<int> dp(partition + 1, 0);
        dp[0] = 1;
        
        for (int num : nombres) {
            for (int p = partition; p >= num; p--) {
                dp[p] += dp[p - num];
            }
        }
        
        return dp[partition];
    }
};

Un et Zéro (LeetCode 474)

Maximiser le nombre de chaînes contenues avec des contraintes sur les 0 et 1.

Sac à dos bidimensionnel

1. Chaque chaîne consomme des 0 (x) et des 1 (y)
2. dp[i][j] = nombre maximal de chaînes pour i zéros et j uns
3. Mise à jour par inclusion de chaque chaîne

class Solution {
public:
    int findMaxForm(vector<string>& chaines, int zeros, int uns) {
        vector<vector<int>> sac(zeros + 1, vector<int>(uns + 1, 0));
        
        for (string& ch : chaines) {
            int x = count(ch.begin(), ch.end(), '0');
            int y = ch.size() - x;
            
            for (int i = zeros; i >= x; i--) {
                for (int j = uns; j >= y; j--) {
                    sac[i][j] = max(sac[i][j], sac[i - x][j - y] + 1);
                }
            }
        }
        
        return sac[zeros][uns];
    }
};