Le sac à dos illimité expliqué : le plan DP derrière le changement de pièce de monnaie

Auteur original：The Logic Blueprint

Source originale：https://www.youtube.com/embed/VrD_ma_wpms

Les principes fondamentaux de la programmation dynamique deviennent beaucoup plus faciles une fois que vous voyez ce qui change réellement entre les problèmes de sac à dos 0/1, de sac à dos illimité, de changement de pièces et de comptage. Dans cette leçon The Logic Blueprint, nous construisons Unbounded Knapsack à partir des premiers principes et montrons pourquoi un petit changement de récurrence change complètement le problème. Vous apprendrez : • ce que signifie réellement « illimité » • comment dériver la récurrence étape par étape • pourquoi la branche de prise reste sur la même ligne • comment réduire la table 2D en DP 1D • pourquoi la direction de la boucle est primordiale • comment le même plan s'étend aux décomptes et aux problèmes d'optimisation. Cette vidéo est destinée aux étudiants, aux apprenants en préparation aux entretiens et aux programmeurs compétitifs qui veulent plus qu'une formule mémorisée. L’objectif est de vous donner un modèle mental réutilisable, pas seulement un problème résolu. Si cela vous a aidé, abonnez-vous à The Logic Blueprint pour des leçons d'algorithme plus approfondies axées sur l'intuition, la structure et le transfert entre les types de problèmes. Ressources pratiques : • Concours éducatif DP AtCoder : https://atcoder.jp/contests/dp • Section de programmation dynamique CSES : https://cses.fi/problemset/ • Minimisation des pièces CSES : https://cses.fi/problemset/task/1634 • Combinaisons de pièces CSES I : https://cses.fi/problemset/task/1635 • Combinaisons de pièces CSES II : https://cses.fi/problemset/task/1636 • Guide USACO, Introduction à DP : https://usaco.guide/gold/intro-dp?lang=cpp • Guide USACO, Knapsack DP : https://usaco.guide/gold/knapsack?lang=cpp • Liste des problèmes de programmation dynamique LeetCode : https://leetcode.com/problem-list/dynamic-programming/ Ordre de pratique suggéré : 1. Minimiser Pièces 2. Combinaisons de pièces I 3. Combinaisons de pièces II 4. Problèmes du concours AtCoder DP 5. Module de sac à dos USACO Guide 6. Variantes LeetCode DP pour le renforcement de style entretien Elles sont particulièrement utiles pour cette vidéo car elles vous obligent à raisonner sur : • les transitions de réutilisation ou d'utilisation unique • l'importance de l'ordre • le nombre par rapport aux objectifs min/max • la compression 2D DP vs 1D DP #programmation dynamique #unboundedknapsack #coinchange #algorithmes #programmationcompétitive