Fiches › Carte › Partie 09 · Coding › coding 09

DP 1D — un sous-problème par position

Une question qui porte sur un préfixe — le meilleur butin sur les i premières maisons, le nombre de façons de monter i marches — et dont la réponse se déduit des réponses sur des préfixes plus courts. Le pattern tient en un geste et trois conséquences : définir dp[i] exactement, puis écrire la récurrence, poser les cas de base, remplir dans l'ordre des dépendances. Ce qui compte n'est pas la récurrence, c'est la définition : « sur le préfixe » et « se terminant en i » ne se lisent pas au même endroit, et confondre les deux rend un nombre plausible et faux. Fil rouge : House Robber (LC 198) sur [2, 7, 9, 3, 1], dp = [2, 7, 11, 11, 12], réponse 12 (maisons 0, 2 et 4). Coût O(n) en temps, O(1) en espace par roulement. Jamais la solution complète : le squelette, la trace, les phrases.

Ce que cette sheet suppose acquis
  • Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Ici il se dit d'un coup : la récurrence est l'invariant, écrit en langage d'indices plutôt qu'en français.
  • Invariant = conteneur + tranche + « exactement ». c00, pas 2. Le conteneur est dp[i], la tranche est le préfixe, et le mot exactement est celui qui décide de tout — c'est le pas 2 de cette sheet en entier.
  • Variant = entier ≥ 0 strictement décroissant. c00, pas 3. C'est n − i, le nombre de positions non encore remplies. Trivial ici, et c'est normal : la difficulté de la DP est entièrement dans l'invariant.
  • Complexité composée. c00, pas 5. Le coût d'une DP se lit nombre d'états × coût d'une transition : n × O(1) pour House Robber, n × O(n) pour la plus longue sous-suite croissante.
  • L'exigence de précision sur l'invariant. c01, pas 3. Même discipline, autre objet : là une tranche [l:r+1), ici une définition de sous-problème. Dans les deux cas le flou ne plante pas, il fausse.
Hypothèses posées
H1L'état tient en un seul indice. Une position sur un axe, un montant, un nombre de marches. Dès qu'il faut deux indices — deux chaînes à aligner, une capacité et une position — c'est de la DP 2D : même rituel, autre sheet. H2Sous-structure optimale. La réponse optimale sur un préfixe se compose de réponses optimales sur des préfixes plus courts. C'est une hypothèse, pas un théorème : elle se vérifie en énonçant le choix fait en i et ce qu'il interdit. H3Les sous-problèmes se chevauchent. C'est ce qui fait de la mémorisation un gain : sans chevauchement, la récursion nue coûte déjà le prix juste et la table ne sert à rien. H4On veut la valeur, pas les choix. Le roulement en O(1) suppose exactement ça : reconstruire les maisons volées demande de garder la table entière — pas 4. H5On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.

La chaîne

Le signal, et le contre-signal tronc

Une question dont la réponse sur les i premiers éléments se déduit des réponses sur moins d'éléments, et un choix à chaque position : prendre ou laisser, couper ou continuer, poser une pièce ou une autre. Les mots qui le trahissent : « nombre de façons », « maximum sur un sous-tableau », « escalier », « pièces », « sans deux adjacents ».

réponse sur un préfixe + un choix par position  ⇒  un sous-problème par position, et une récurrence

Le contre-signal est double. Si le sous-problème dépend de tout le futur — un tableau circulaire, une contrainte globale — le préfixe ne porte plus l'information et la récurrence n'existe pas. Si l'état demande deux indices, c'est de la DP 2D.

« La réponse sur les i premiers se déduit des réponses sur moins d'éléments, donc il existe un sous-problème par position, donc la question devient une récurrence à remplir dans l'ordre, donc un seul passage suffit. »

Application — le fil rouge, et ce que le contre-signal coûte

Le fil rouge. House Robber, LC 198 : nums = [2, 7, 9, 3, 1], on maximise la somme sans prendre deux maisons adjacentes. Réponse 12 = 2 + 9 + 1, maisons 0, 2, 4. Vérifié par force brute sur chaque préfixe : 2 · 7 · 11 · 11 · 12, exactement la table dp.

Pourquoi cet exemple et pas un autre. C'est l'exemple canonique de LC 198, et il contient le seul tour qui prouve quelque chose : au tour i = 3 la table stagne (11 → 11). Un exemple où dp croît à chaque tour laisserait croire qu'on additionne ; ici on voit qu'on choisit.

Le contre-signal, chiffré. Sur [5, −3, 5], le meilleur sous-tableau linéaire vaut 7 (tout le tableau) ; le meilleur sous-tableau circulaire vaut 10, en recollant les deux 5 par les bords. Un dp sur les préfixes ne verra jamais 10 : la solution n'est pas un préfixe d'un suffixe. Le remède se dit en une phrase — total − (somme minimale d'un sous-tableau) — et il rend au problème son axe.

Ce que la sheet n'aborde pas. La DP 2D (distance d'édition, sac à dos, grilles), la DP sur arbres, la DP à bitmask. On les nomme si la question tombe ; ici, un seul indice et un seul passage.

Définir le sous-problème exactement : le geste qui décide de tout tronc

Deux définitions circulent sous le même nom, et elles ne se lisent pas au même endroit. Sur le préfixe : dp[i] = la réponse sur nums[0:i+1], l'élément i pouvant être laissé. Se terminant en i : dp[i] = la réponse parmi les solutions qui utilisent i.

dp sur le préfixe  ⇒  réponse = dp[n−1]  ·  dp « se terminant en i »  ⇒  réponse = maxi dp[i]

La seconde est souvent la seule qui donne une récurrence simple — c'est le cas de Kadane et de la sous-suite croissante. Elle se paie d'un max final, et c'est exactement ce max qu'on oublie.

« Une solution se termine quelque part, donc fixer cette fin donne un sous-problème par position, donc la récurrence devient simple, donc la réponse n'est plus la dernière case mais le maximum sur toutes les cases. »

Application — les deux définitions sur le fil rouge, chiffrées
dp sur le préfixe — celle de House Robberdp[i] = butin max sur nums[0:i+1] · [2, 7, 11, 11, 12] · réponse lue en dp[4] = 12
dp « se terminant en i » — la même entréedp[i] = butin max en volant i · [2, 7, 11, 10, 12] · réponse = max = 12, atteint en i = 4 par coïncidence

Deux tables différentes, même réponse ici : c'est ce qui rend la confusion durable.

Le contre-exemple minimal. Sur [5, 1, 1, 0], la table « se terminant en i » vaut [5, 1, 6, 5] : le maximum est 6 (voler 0 et 2), mais la dernière case vaut 5. Lire dp[n−1] au lieu du max rend 5 au lieu de 6 — un nombre plausible, sans la moindre exception.

Le test qui tranche, à se poser à voix haute. « Est-ce que dp[i] a le droit de ne pas utiliser l'élément i ? » Oui ⇒ définition préfixe, la réponse est la dernière case. Non ⇒ définition « se terminant en i », la réponse est un max. Il n'y a pas de troisième cas, et la question se pose avant d'écrire la récurrence.

Et « jusqu'à i » ? C'est la formule à bannir : elle ne dit ni si i est inclus, ni s'il est utilisé. Deux lecteurs en tirent deux tables, deux cas de base, deux décalages d'indice — et le code tourne dans les deux cas.

La récurrence est l'invariant ; cas de base, ordre de remplissage tronc

Une fois dp[i] défini, la récurrence s'obtient en énonçant le choix fait en i et ce qu'il interdit. Voler la maison i interdit la maison i − 1, donc le reste du butin se lit en dp[i − 2] :

dp[i] = max( dp[i−1] , dp[i−2] + nums[i] )  ·  dp[0] = nums[0]  ·  dp[1] = max(nums[0], nums[1])

L'ordre de remplissage n'est pas une convention : dp[i] lit dp[i−1] et dp[i−2], donc i croissant. Variant : n − i. Conclusion : à i = n − 1, la tranche vaut le tableau entier.

« Voler i interdit i − 1, donc le butin en volant i vaut dp[i−2] + nums[i], donc dp[i] est le max de ce butin et de dp[i−1], donc remplir dans l'ordre croissant tient l'invariant à chaque case et dp[n−1] est le butin maximal sur tout le tableau. »

Application — le squelette, puis l'invariant récité sur les cinq tours
a, b = 0, 0 # a = dp[i−2] # b = dp[i−1] pour v dans nums : # dp[i] = max(laisser i, prendre i) a, b = b, max(b, a + v) retour b

Quatre lignes de code, et deux portent l'idée : max(b, a + v) est la récurrence, a, b = b, … est l'ordre de remplissage. Les cas de base ne sont pas écrits : (0, 0) les produit — au premier tour on obtient max(0, 0 + 2) = 2 = dp[0], au deuxième max(2, 0 + 7) = 7 = dp[1].

  • i = 0, v = 2. max(0, 0 + 2) = 2. Butin max sur [2]. ✔
  • i = 1, v = 7. max(2, 0 + 7) = 7 — on abandonne la maison 0. Butin max sur [2, 7]. ✔
  • i = 2, v = 9. max(7, 2 + 9) = 11 — on vole, et la maison 0 revient dans la solution : {0, 2}.
  • i = 3, v = 3. max(11, 7 + 3) = 11 — la table stagne : voler 3 rapporterait 10, moins que les 11 déjà acquis. La solution reste {0, 2}.
  • i = 4, v = 1. max(11, 11 + 1) = 12 — on vole 1, qui ne coûte rien : la maison 3 n'était pas prise. Solution {0, 2, 4}.
  • Conclusion. Variant nul donc la tranche vaut nums tout entier donc b = dp[4] = 12 est le butin maximal.

Vérifié à l'exécution. La table confrontée à l'énumération de tous les sous-ensembles sans deux adjacents, sur 20 000 tirages (longueurs 1 à 10, valeurs 0 à 20) : 0 désaccord. Et sur chacun des cinq préfixes du fil rouge, la force brute rend le même optimum et le même jeu de maisons.

Figure 1 — les cinq tours de LC 198, la récurrence à chaque image

nums = [2, 7, 9, 3, 1]. Le fond ambré est un jeu de maisons optimal pour le préfixe courant — celui que la table représente, recalculé par force brute à chaque image. Fais « pas › » et regarde deux choses. D'abord ce que la récurrence lit : jamais plus que dp[i−1] et dp[i−2], jamais le tableau entier — c'est ce qui autorisera le roulement du pas 4. Ensuite l'image 4, la seule qui prouve quelque chose : dp stagne à 11, donc la maison 3 est refusée ; le fond ambré ne bouge pas. Une table qui croît à chaque tour, ce serait une somme ; une table qui stagne, c'est un choix. Et note l'image 2 : la maison 0 sort de la solution, puis revient à l'image 3 — dp[i] retient une valeur, pas un jeu de maisons, et c'est pour cela que reconstruire les choix demande de garder la table.

Le roulement : ne garder que ce que la récurrence lit

La table entière n'a jamais été nécessaire : elle est un artefact de la façon dont on a écrit la récurrence. Si dp[i] ne lit que k termes précédents, k variables suffisent — deux ici. La table ne redevient obligatoire que pour reconstruire les choix.

temps = états × transition = n × O(1) = O(n)  ·  espace O(1) si la récurrence lit k termes fixes, O(n) si on reconstruit

Et l'autre moitié du gain se voit en face : la récursion nue recalcule les mêmes sous-problèmes en boucle. C'est le chevauchement (H3) que la table encaisse, pas la récurrence.

« La récurrence ne lit que deux termes, donc deux variables portent tout l'état, donc l'espace tombe à O(1) — et si on me demande les maisons volées et pas seulement le butin, je garde la table et je remonte depuis la fin. »

Application — mesuré, pas estimé

Ce que la mémorisation achète. House Robber écrit en récursion nue, appels comptés : 287 appels à n = 10, 35 421 à n = 20, 392 835 à n = 25, 4 356 617 à n = 30 — contre 30 tours en DP. Le rapport n'est pas un facteur, c'est un changement de classe : O(φn) contre O(n).

Ce que le roulement achète. n = 106, même entrée : roulement 0,08 s et deux entiers ; table complète 0,12 s et 8,0 Mo de liste. Même réponse aux deux. Le gain en temps est marginal, le gain en espace est le seul qui se dit — et c'est celui qu'on demande en entretien.

Reconstruire les choix, quand on les veut. On garde dp, on part de i = n − 1 et on remonte : si dp[i] = dp[i−1], la maison i n'a pas été volée, on recule d'un cran ; sinon elle l'a été, on recule de deux. Sur le fil rouge : 12 ≠ 11 donc on prend 4 ; 11 = 11 donc on saute 3 ; 11 ≠ 7 donc on prend 2 ; puis 0. Jeu {0, 2, 4}, celui de la force brute.

La phrase qui rapporte des points. « Je pars du tableau dp — c'est lui qui rend l'invariant lisible — puis je remarque que la récurrence ne lit que deux cases, donc je roule. » Annoncer O(1) d'emblée fait sauter l'étape où l'invariant se démontre.

Les variantes : même geste, une autre récurrence

La charpente ne bouge pas — définir dp, écrire la récurrence, poser les cas de base, remplir dans l'ordre. Ce qui change est la définition, et elle commande tout le reste : où se lit la réponse, dans quel ordre on remplit, ce qu'on peut oublier.

Kadane : dp[i] = max( nums[i] , dp[i−1] + nums[i] )  ·  réponse = maxi dp[i]

Kadane est une DP, et c'est la seule façon de ne plus l'apprendre par cœur : dp[i] est la meilleure somme finissant en i, le max intérieur décide de repartir, et le max extérieur est la réponse.

« dp[i] est la meilleure somme finissant en i, donc soit on prolonge le sous-tableau précédent, soit on repart de i seul, donc on repart dès que dp[i−1] est négatif, donc la réponse est le maximum de la table et non sa dernière case. »

Application — quatre variantes, chacune avec sa définition et ses chiffres
Kadane — somme max d'un sous-tableau, LC 53dp[i] = meilleure somme finissant en i · cur = max(x, cur + x), best = max(best, cur) · sur [−2, 1, −3, 4, −1, 2, 1, −5, 4] : 6, sur [4, −1, 2, 1] · on repart aux indices 1 et 3 · O(n) / O(1)
Escalier — nombre de façons, LC 70dp[i] = nombre de façons d'atteindre la marche i (préfixe) · dp[i] = dp[i−1] + dp[i−2] · n = 1…10 : 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 — c'est F(n+1), un comptage et non un optimum · O(n) / O(1)
Pièces, minimum — LC 322dp[m] = nombre minimal de pièces pour le montant m · dp[m] = 1 + min(dp[m − c]) · l'indice n'est plus une position mais un montant, donc l'ordre de remplissage est croissant en montant · pièces [1, 3, 4], montant 6 : dp = [0, 1, 2, 1, 1, 2, 2], réponse 2 (3 + 3) · O(m × |c|)
Plus longue sous-suite croissante — LC 300dp[i] = longueur max d'une sous-suite croissante finissant en i · dp[i] = 1 + max(dp[j] : j < i, a[j] < a[i]) · sur [10, 9, 2, 5, 3, 7, 101, 18] : dp = [1, 1, 1, 2, 2, 3, 4, 4], réponse 4 sur [2, 5, 7, 101] · O(n²) : la transition coûte O(n)

Deux tables « finissant en i » sur quatre — donc deux max finaux à ne pas oublier. Et la LIS en O(n log n) n'est plus une DP : c'est un tableau de queues maintenu trié, dans lequel on fait une recherche dichotomique.

Le glouton ne remplace pas la DP. Sur les pièces [1, 3, 4] et le montant 6, le glouton prend la plus grosse pièce d'abord : 4 + 1 + 1 = 3 pièces. La DP en trouve 2 : 3 + 3. Le glouton rend un nombre valide, jamais une erreur — c'est le même mode de panne qu'au pas 6.

L'impossible se marque, il ne se devine pas. Pièces [2], montant 3 : dp = [0, +∞, 1, +∞], donc −1. Sans le +∞, un min sur une liste vide lève un ValueError — et un 0 par défaut, lui, ne lève rien et prétend que 3 se paie sans pièce.

Figure 2 — Kadane, ou pourquoi « repartir » est un max et pas une astuce

nums = [−2, 1, −3, 4, −1, 2, 1, −5, 4]. Le cadre vert est le sous-tableau courant — celui dont cur est la somme ; le fond ambré est le meilleur sous-tableau enregistré jusqu'ici. Fais « pas › » et regarde le cadre vert : il ne fait que deux choses, s'allonger d'une case ou repartir à un. Les deux images qui comptent sont la 2 et la 4, les seules où il repart : à chaque fois cur était négatif, donc le traîner coûterait plus qu'il ne rapporte — c'est tout le contenu de max(x, cur + x). Puis regarde la fin : à la dernière image cur vaut 5 et best vaut 6. La table « finissant en i » ne met pas sa réponse dans la dernière case, et retourner cur rendrait ici 5 au lieu de 6 — sans erreur, sans ralentissement, sans avertissement.

Où ça casse casse

La DP casse par le haut, sur la définition. Un dp[i] flou — « la réponse jusqu'à i » — se traduit malgré tout en une récurrence, des cas de base et une boucle qui tourne. Rien ne plante, rien ne ralentit : il sort un nombre du bon ordre de grandeur, et il est faux.

définition floue  ⇒  récurrence fausse ou réponse lue au mauvais endroit  ⇒  nombre plausible, zéro exception

C'est le mode de panne le plus coûteux de toute la série : un test sur l'exemple de l'énoncé passe souvent, et l'erreur n'apparaît que sur une entrée qu'on n'a pas pensé à construire.

« Le code tourne et rend un nombre, donc rien ne signale l'erreur, donc le seul garde-fou est d'énoncer dp[i] avec le mot “exactement” et de dire où se lit la réponse, donc je fais les deux à voix haute avant d'écrire la boucle. »

Les trois pannes silencieuses, à sortir de mémoire

Le max final oublié. Kadane sur le fil rouge de la figure 2 : retourner cur au lieu de best rend 5 au lieu de 6. Sur 20 000 tirages aléatoires (longueurs 1 à 9, valeurs −9 à 9), cur et best diffèrent dans 51,1 % des cas : ce n'est pas un cas limite, c'est plus d'une entrée sur deux.

La dernière case lue au lieu du max. House Robber avec une table « se terminant en i » sur [5, 1, 1, 0] : dp = [5, 1, 6, 5]. Le maximum vaut 6, la dernière case 5. Même famille que la précédente, même absence d'erreur — et sur le fil rouge [2, 7, 9, 3, 1] les deux lectures donnent 12, donc l'exemple de l'énoncé ne l'aurait pas attrapé.

L'ordre de remplissage inversé. Pièces [1, 3, 4], montant 6, montants parcourus en décroissant : dp = [0, 1, +∞, 1, 1, +∞, +∞]. La fonction répond « impossible » pour 6, dont la vraie réponse est 2 — et « impossible » est une réponse que l'énoncé prévoit, donc elle ne choque personne. La règle : remplir dans l'ordre des dépendances, et dp[m] dépend de dp[m − c], qui est plus petit.

La phrase qui tue. « Je dis dp[i] en entier, avec “exactement”, et je dis où se lit la réponse — dernière case ou maximum. Si je ne peux pas dire les deux, je n'écris pas encore la récurrence. »

Pièges Python — quatre lignes qui ont l'air justes
  • Le roulement écrit en deux affectations. a = b puis b = max(b, a + v) : a est écrasé avant d'être lu, donc on additionne deux voisines. Sur le fil rouge, 22 au lieu de 12 — vérifié. Et 22 > 12 : le bug rend un butin meilleur, ce qui n'éveille aucun soupçon. Remède : a, b = b, max(b, a + v), une seule affectation, le membre de droite entièrement évalué d'abord.
  • Les cas de base bricolés. Deux écoles, et une seule à choisir : soit dp[0] et dp[1] écrits à la main — et alors nums de longueur 1 lève un IndexError — soit le roulement initialisé à (0, 0), qui produit les deux premiers tours (max(0, 0 + 2) = 2, puis max(2, 0 + 7) = 7) et traite la longueur 1 sans cas particulier. Vérifié : les deux donnent [2, 7, 11, 11, 12].
  • best = 0 pour Kadane. Faux dès que tout est négatif : [−3, −1, −2] rend 0 au lieu de −1, un sous-tableau vide n'étant pas un sous-tableau. Sur 20 000 tirages, l'initialisation à 0 est fausse dans 9,9 % des cas. Remède : cur = best = nums[0], puis la boucle à partir de l'indice 1.
  • Le +∞ des pièces. float('inf') pour les montants inatteignables, et la conversion en −1 à la sortie — pas pendant. Initialiser à 0 fait croire que tout montant se paie sans pièce ; un min() sur un générateur vide lève un ValueError ; et dp[m − c] + 1 sur inf vaut inf, ce qui est exactement le comportement voulu.

Résumé

À retenir
  1. Signal : une réponse sur un préfixe déduite des préfixes plus courts, et un choix par position. Contre-signal : le sous-problème dépend de tout le futur (circulaire), ou l'état demande deux indices (DP 2D).
  2. Le geste : définir dp[i] exactement. « Sur le préfixe [0:i+1] » ⇒ réponse = dp[n−1] · « se terminant en i » ⇒ réponse = maxi dp[i]. Le test : dp[i] a-t-il le droit de ne pas utiliser i ?
  3. La récurrence est l'invariant : on énonce le choix fait en i et ce qu'il interdit. House Robber : dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Variant : n − i.
  4. Cas de base et ordre de remplissage : on remplit dans l'ordre des dépendances. Pour les pièces c'est le montant croissant — à l'envers, dp[6] sort « impossible » au lieu de 2.
  5. Roulement : la récurrence ne lit que deux termes ⇒ deux variables, espace O(1), temps O(n). La table complète ne sert qu'à reconstruire les choix ({0, 2, 4} sur le fil rouge).
  6. Variantes : Kadane = dp « finissant en i » + max final (6 sur le fil rouge) · escalier = Fibonacci (89 pour 10 marches) · pièces = min + +∞ + ordre croissant · LIS = O(n²), et sa version O(n log n) est une dichotomie.
  7. Où ça casse : la définition floue. Kadane sans max final rend 5 au lieu de 6 (et diffère dans 51,1 % des tirages) ; la table « finissant en i » lue en dernière case rend 5 au lieu de 6 sur [5, 1, 1, 0] — sans aucune erreur.
« Je définis dp[i] exactement — sur le préfixe ou se terminant en i — j'écris la récurrence, qui est mon invariant, je pose les cas de base et je remplis dans l'ordre des dépendances. Si la récurrence ne lit que deux termes, je roule en O(1). Kadane, c'est dp “se terminant en i” avec un max final : on repart quand le passé pèse. »

Chaîne verbalisée — une prise, à voix haute

5 maillons · clique pour révéler après avoir dit
  1. Comment définis-tu dp[i], et pourquoi la précision compte-t-elle ?
    Deux définitions et pas une : dp[i] = la réponse sur le préfixe nums[0:i+1], où i a le droit de ne pas être utilisé ; ou dp[i] = la réponse parmi les solutions qui utilisent i, « se terminant en i ». La première se lit en dp[n−1], la seconde exige un max sur tous les i. Le test qui tranche : est-ce que dp[i] a le droit de ne pas utiliser l'élément i ? « La réponse jusqu'à i » ne dit ni l'un ni l'autre, et le code tourne quand même — c'est de là que vient la faute.
  2. La récurrence de House Robber, et son invariant ?
    dp[i] = max(dp[i−1], dp[i−2] + nums[i]) : voler i interdit i−1, donc ce qui reste se lit deux cases plus tôt. L'invariant est la récurrence elle-même : après le tour i, b = dp[i] = le butin maximal sur nums[0:i+1] exactement, et a = dp[i−1]. Cas de base dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) — ou le roulement à (0, 0), qui les produit. Variant n − i. Conclusion : à i = n−1, b est le butin maximal sur tout le tableau. Sur [2, 7, 9, 3, 1] : 2, 7, 11, 11, 12.
  3. Quand roule-t-on en O(1), et quand ne le peut-on pas ?
    Dès que la récurrence ne lit qu'un nombre fixe de termes précédents : deux ici, donc deux variables, a, b = b, max(b, a + v) en une seule affectation. Temps O(n) — n états × transition O(1) — et espace O(1). On ne le peut pas si on veut reconstruire les choix : il faut alors garder la table et remonter depuis la fin, en comparant dp[i] à dp[i−1]. Sur le fil rouge ça rend {0, 2, 4}. Mesuré à n = 10⁶ : 8,0 Mo de table contre deux entiers, pour la même réponse.
  4. Kadane : que vaut dp[i], et d'où vient la réponse ?
    dp[i] est la meilleure somme d'un sous-tableau finissant en i : soit on prolonge le précédent, soit on repart de i tout seul, donc cur = max(x, cur + x). On repart exactement quand cur est négatif — le passé pèse plus qu'il ne rapporte. La réponse n'est pas dp[n−1] mais le maximum de la table, d'où best = max(best, cur) à chaque tour. Sur [−2, 1, −3, 4, −1, 2, 1, −5, 4] : 6, sur [4, −1, 2, 1] ; à la fin cur vaut 5 et best vaut 6.
  5. Qu'est-ce qui casse sans lever d'erreur ?
    Tout ce qui touche à la définition. Kadane sans le max final rend 5 au lieu de 6 sur le fil rouge, et diffère dans 51,1 % des tirages aléatoires. Une table « se terminant en i » lue en dernière case rend 5 au lieu de 6 sur [5, 1, 1, 0]. Les pièces remplies en montant décroissant rendent « impossible » pour un montant qui coûte 2 pièces. Et le roulement écrit en deux affectations rend 22 au lieu de 12 — un butin plus grand que le vrai, donc invisible. Dans les quatre cas : un nombre plausible, aucune exception, aucun ralentissement.