198. Maison Voleur

Ce problème est analogue à une version non continue de la somme maximale d'une sous-séquence. En séparant le dernier élément, les parties précédentes forment un sous-problème. La solution utilise la programmation dynamique pour calculer le maximum sans voler deux maisons adjacentes.

class Solution {
public:
    int rob(vector<int>& maison) {
        int n = maison.size();
        if (n == 0) return 0;
        if (n == 1) return maison[0];
        vector<int> memo(n);
        memo[0] = maison[0];
        memo[1] = max(maison[0], maison[1]);
        for (int i = 2; i < n; ++i) {
            memo[i] = max(memo[i - 1], memo[i - 2] + maison[i]);
        }
        return memo[n - 1];
    }
};</int></int>

279. Carrés Pafraits

Cette question ressemble à une approche gloutonde, où l'optimalité locale mène à l'optimalité globale. On utilise la programmation dynamique pour déterminer le nombre minimum de carrés parfaits qui somment à n.

class Solution {
public:
    int numSquares(int n) {
        int racine = sqrt(n);
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= racine; ++j) {
                int carre = j * j;
                if (i >= carre && dp[i - carre] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - carre] + 1);
                }
            }
        }
        return dp[n];
    }
};</int>

300. Sous-séquence Strictement Croissante la Plus Longue

Cette sous-séquence peut être non continue, ce qui la distingue des problèmes continus. L'état est la longueur de la sous-séquence se terminant à l'indice i, et l'opération consiste à parcourir les indices précédents pour étendre la séquence si possible.

class Solution {
public:
    int lengthOfLIS(vector<int>& suite) {
        int taille = suite.size();
        vector<longeur> longueur(taille, 1);
        for (int i = 1; i < taille; ++i) {
            for (int j = 0; j < i; ++j) {
                if (suite[i] > suite[j]) {
                    longueur[i] = max(longueur[i], longueur[j] + 1);
                }
            }
        }
        int resultat = 0;
        for (int long_val : longueur) {
            resultat = max(resultat, long_val);
        }
        return resultat;
    }
};</longeur></int>

322. Rendu de Monnaie

Ce problème nécessite de gérer des placeholders lorsque les positions ne sont pas encore calculées. La programmation dynamique est utilisée pour trouver le minimum de pièces pour atteindre un montant donné, en évitant les valeurs invalides.

class Solution {
public:
    int coinChange(vector<int>& pieces, int montant) {
        vector<int> memo(montant + 1, -1);
        memo[0] = 0;
        for (int i = 1; i <= montant; ++i) {
            for (int piece : pieces) {
                if (i >= piece && memo[i - piece] != -1) {
                    int candidat = memo[i - piece] + 1;
                    if (memo[i] == -1) {
                        memo[i] = candidat;
                    } else {
                        memo[i] = min(memo[i], candidat);
                    }
                }
            }
        }
        return memo[montant];
    }
};</int></int>