Glouton ou DP : quand utiliser chaque approche
Identifiez les caractéristiques des problèmes résolubles par une approche gloutonne et de ceux qui nécessitent DP, en utilisant la propriété du choix glouton et l’argument d’échange.
Glouton ou DP : quand utiliser chaque approche est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Vue d’ensemble des approches gloutonne et DP
Les approches gloutonne et de programmation dynamique résolvent des problèmes d’optimisation : trouver un maximum, un minimum ou une disposition optimale. Une approche gloutonne effectue le choix localement optimal à chaque étape sans revenir sur les décisions précédentes. La DP explore toutes les possibilités, mais utilise la mémoïsation pour éviter les recalculs. Savoir laquelle appliquer peut vous épargner des heures de débogage d’une approche gloutonne incorrecte ou d’un tableau de DP inutilement complexe.
# Greedy: always take the locally best option
# Example: coin change with coins [1, 5, 10, 25]
# Greedy: take as many 25s as possible, then 10s, etc.
# This works for standard denominations but NOT all coin sets!
# DP: explore all possibilities via memoisation
# Example: coin change with coins [1, 3, 4] and target 6
# Greedy would pick 4, then 1, 1 → 3 coins
# DP finds: 3 + 3 → 2 coins (optimal!)
print('Greedy can fail when local optimum != global optimum')La propriété du choix glouton
Un problème possède la propriété du choix glouton lorsqu’une solution globalement optimale peut toujours être construite en effectuant des choix localement optimaux (gloutons). Formellement, il existe une solution optimale qui commence par le choix glouton, de sorte qu’il n’est jamais nécessaire d’effectuer un retour arrière. Pour le démontrer, on utilise généralement un argument d’échange : supposez qu’une solution optimale quelconque n’inclut pas le choix glouton, puis montrez que vous pouvez l’y échanger sans détériorer le résultat.
# Exchange argument example: Activity Selection
# Greedy: always pick the activity that ends earliest
# Proof: suppose optimal solution starts with activity A (not earliest-ending)
# Let G be the earliest-ending activity.
# Replace A with G in the solution:
# - G ends no later than A, so G does not conflict with any activity A allowed
# - The solution remains valid with at least as many activities
# Therefore greedy choice (earliest end) is always safe.
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
activities.sort(key=lambda x: x[1]) # sort by end time
print('Sorted by end:', activities[:4], '...')Sous-structure optimale
Les approches gloutonne et DP nécessitent toutes deux une sous-structure optimale : la solution optimale du problème complet contient des solutions optimales de ses sous-problèmes. La différence tient à la possibilité de déterminer ou non les solutions optimales des sous-problèmes de manière gloutonne (sans explorer toutes les options), ou à la nécessité de comparer plusieurs choix. Si vous effectuez un choix et que le sous-problème restant possède une structure identique, l’approche gloutonne fonctionne. Si vous devez comparer plusieurs choix, utilisez la DP.
# Greedy works: activity selection
# Making the greedy choice (earliest-ending) leaves a sub-problem
# that is structurally identical (activity selection on remaining activities)
# and the greedy choice for the sub-problem is still valid.
# DP needed: 0/1 knapsack
# After choosing to include/exclude item i, the remaining sub-problem
# depends on WHICH item we chose — different choices yield different sub-problems.
# No single greedy rule works for all inputs.
print('Greedy: sub-problem is unique after each choice')
print('DP: sub-problem depends on which choice was made')Les sous-problèmes qui se chevauchent : un signal pour utiliser DP
Si le même sous-problème est résolu plusieurs fois lors d’une décomposition récursive, la DP avec mémoïsation est nécessaire. Dessinez l’arbre de récursion et recherchez les nœuds répétés. Pour Fibonacci, fib(3) est calculé deux fois dans l’arbre de fib(5). Pour le rendu de monnaie avec les pièces [1,3,4] et une cible de 6, les sous-problèmes correspondant aux cibles 3, 2 et 1 apparaissent plusieurs fois. Sous-problèmes qui se chevauchent + sous-structure optimale = DP.
# Recursion tree for coin change [1,3,4], target=6
# bt(6) → bt(5) → bt(4) → bt(3) (repeated!)
# → bt(2) → bt(1) (repeated!)
# → bt(3) (repeated!)
# → bt(2) (repeated!)
# Without memoisation: exponential time
# With DP table: O(target * len(coins)) time
def coin_change_dp(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_dp([1, 3, 4], 6)) # 2 (3+3)
print(coin_change_dp([2], 3)) # -1 (impossible)Problèmes classiques résolus par une approche gloutonne
Problèmes pour lesquels l’approche gloutonne est démontrée correcte : (1) planification d’activités ou d’intervalles — approche gloutonne fondée sur l’heure de fin la plus proche ; (2) arbre couvrant de poids minimal — algorithmes de Prim et de Kruskal ; (3) codage de Huffman — fusionner toujours les deux nœuds de plus faible fréquence ; (4) sac à dos fractionnaire — choisir les éléments selon le rapport valeur/poids le plus élevé ; (5) jeu des sauts — suivre l’indice maximal atteignable. Tous ces problèmes se justifient par une démonstration fondée sur un argument d’échange.
# Fractional Knapsack: greedy works
def fractional_knapsack(items, capacity):
# Sort by value/weight ratio descending
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total = 0
for weight, value in items:
if capacity <= 0: break
take = min(weight, capacity)
total += take * (value / weight)
capacity -= take
return total
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
print(fractional_knapsack(items, 50)) # 240.0
# 0/1 Knapsack: greedy FAILS
# Must use DP (can't take fractions)Quand l’approche gloutonne échoue : contre-exemples
Trouver un contre-exemple est le moyen le plus rapide de réfuter une hypothèse gloutonne. Pour le rendu de monnaie avec les pièces [1, 3, 4] et une cible de 6, l’approche gloutonne (plus grande pièce d’abord) choisit 4, puis 1+1, soit 3 pièces. La DP trouve 3+3, soit 2 pièces. Pour le problème du sac à dos 0/1, une approche gloutonne fondée sur le rapport choisit l’élément au meilleur rapport, mais peut manquer des combinaisons qui remplissent mieux la capacité. Si vous pouvez construire un contre-exemple en moins d’une minute, passez à la DP.
# Counterexample: coin change with non-standard coins
def greedy_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for c in coins:
while amount >= c:
amount -= c
count += 1
return count if amount == 0 else -1
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] if dp[amount] < float('inf') else -1
coins, target = [1, 3, 4], 6
print('Greedy:', greedy_coins(coins[:], target)) # 3 (4+1+1)
print('DP: ', dp_coins(coins, target)) # 2 (3+3)Tableau comparatif : approche gloutonne et DP
Principales différences côte à côte : complexité temporelle — l’approche gloutonne est généralement en O(n log n) (le tri domine) ; la DP est en O(n × états). Complexité spatiale — l’approche gloutonne utilise O(1) espace auxiliaire ; la DP utilise O(états). Exactitude — l’approche gloutonne nécessite une démonstration ; la DP est toujours correcte si les états et la récurrence sont justes. Applicabilité — l’approche gloutonne convient à la planification, aux arbres couvrants et au codage de Huffman ; la DP convient au sac à dos, à l’alignement de séquences et aux plus courts chemins avec des poids négatifs.
# Performance comparison
import time
def time_it(func, *args):
start = time.time()
result = func(*args)
return result, time.time() - start
# Large coin change test
coins = [1, 5, 10, 25, 100]
amount = 10000
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c]+1)
return dp[amount]
result, elapsed = time_it(dp_coins, coins, amount)
print(f'DP coin change(amount={amount}): {result} coins in {elapsed:.4f}s')Cadre de décision
Organigramme de décision pour un entretien : (1) Pouvez-vous démontrer la propriété du choix glouton avec un argument d’échange ? Si oui → approche gloutonne. (2) Les sous-problèmes se chevauchent-ils (le même état est-il atteint de plusieurs manières) ? Si oui → DP. (3) Le problème demande-t-il de compter ou d’énumérer toutes les solutions ? → DP ou retour arrière. (4) Le problème demande-t-il une seule valeur optimale avec un ordre naturel ? Envisagez une approche gloutonne. (5) En cas de doute, implémentez la DP : elle est toujours correcte si la récurrence est juste, même si elle est plus lente.
# Decision questions to ask:
questions = [
'1. Is there a natural ordering (by time, ratio, size)?',
'2. Does making the greedy choice leave a smaller same-type problem?',
'3. Can I construct a counterexample quickly?',
'4. Are sub-problems reused across different choice sequences?',
'5. Does the problem involve counting or listing (not just optimising)?',
]
for q in questions:
print(q)
print()
print('Greedy signals: scheduling, spanning tree, Huffman, jump game')
print('DP signals: knapsack, edit distance, LCS, coin change (general)')Problèmes d’intervalles : approche gloutonne ou DP
Les problèmes d’intervalles se répartissent entre approche gloutonne et DP. Pour les intervalles non chevauchants (en supprimer le moins possible), triez selon l’heure de fin et sélectionnez les intervalles de manière gloutonne : l’approche gloutonne est démontrée optimale. Pour la planification pondérée d’intervalles (maximiser le poids total), la DP est nécessaire, car des intervalles lourds peuvent chevaucher de nombreux intervalles légers, ce qui impose de comparer tous les sous-ensembles valides. Le facteur déterminant est de savoir si tous les intervalles ont un poids égal (approche gloutonne) ou un poids variable (DP).
# Non-overlapping intervals: greedy works
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1])
count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
count += 1 # remove this interval
return count
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2Reconnaître les indices d’un problème
Indices fréquents dans les énoncés : « nombre minimal d’opérations », « profit maximal », « sélection optimale » → l’approche peut être gloutonne ou fondée sur la DP ; vérifiez les chevauchements. « compter le nombre de façons » → toujours la DP. « trouver une planification valide » → l’approche peut être gloutonne. « toutes les possibilités » → retour arrière. « impossible de prendre des éléments adjacents » → DP (problème du voleur de maisons). « réunions, intervalles, tâches » → probablement une approche gloutonne. Associer les indices aux familles d’algorithmes accélère le diagnostic des problèmes d’entretien.
# Signal-to-algorithm mapping
signals = {
'minimum steps/coins/operations': 'DP (unless trivially greedy)',
'maximum profit/value with constraint': 'DP (knapsack family)',
'count ways to reach/achieve': 'DP (always)',
'all combinations/permutations': 'Backtracking',
'schedule tasks within time': 'Greedy (sort by deadline/end)',
'cannot pick adjacent': 'DP (house robber pattern)',
'free to pick any subset': 'DP or Greedy (check overlap)',
'interval merging/selecting': 'Greedy (sort by end time)',
}
for signal, algo in signals.items():
print(f'{signal!r}: → {algo}')Démontrer l’exactitude de l’approche gloutonne
Pour démontrer qu’un algorithme glouton est correct, utilisez l’argument d’échange : (1) supposez qu’il existe une solution optimale OPT qui diffère de la solution gloutonne G au premier choix ; (2) montrez que vous pouvez échanger le choix glouton dans OPT sans augmenter la valeur de l’objectif ; (3) par récurrence, la solution gloutonne est aussi bonne que toute solution optimale. Lors d’un entretien, une démonstration complète n’est pas nécessaire, mais expliquer l’intuition de l’argument d’échange témoigne d’une compréhension approfondie.
# Exchange argument demo: earliest-finish-time activity selection
# Suppose OPT starts with activity A (not earliest-ending)
# Let G = earliest-ending activity available
# A.end >= G.end (G ends earlier or same time)
# Swap A for G in OPT:
# - G.end <= A.end, so G does not conflict with anything A allowed after it
# - OPT remains valid with the same number of activities
# - Repeat: after swap, OPT begins with G, matching greedy first choice
# By induction, OPT can be transformed to match G activity by activity
# without losing activities → greedy is optimal
print('Exchange argument: any OPT can be modified to match Greedy without loss')
print('This proves Greedy >= OPT in objective value')Vérification rapide
Vérifiez votre compréhension des concepts de structures de données & algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : l’approche gloutonne est correcte lorsque la propriété du choix glouton est vérifiée, ce qui se démontre par un argument d’échange ; la DP est nécessaire lorsque les sous-problèmes se chevauchent (le même sous-problème est atteint de plusieurs manières) et ne peuvent pas être résolus par une seule règle gloutonne ; et le moyen le plus rapide de réfuter une hypothèse gloutonne consiste à construire un contre-exemple avec des entrées atypiques. La prochaine étape consiste à résoudre des problèmes de planification et de fusion d’intervalles avec l’approche gloutonne fondée sur le tri selon l’heure de fin.
Questions Fréquemment Posées
La leçon « Glouton ou DP : quand utiliser chaque approche » est-elle gratuite ?
Oui — le texte complet de « Glouton ou DP : quand utiliser chaque approche » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Glouton ou DP : quand utiliser chaque approche » ?
Identifiez les caractéristiques des problèmes résolubles par une approche gloutonne et de ceux qui nécessitent DP, en utilisant la propriété du choix glouton et l’argument d’échange. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Glouton ou DP : quand utiliser chaque approche » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Glouton ou DP : quand utiliser chaque approche
- Planification et fusion d’intervalles
- Jeu des sauts I et II
- Planificateur de tâches et station-service