Quand avez-vous utilisé la programmation dynamique sur le terrain?

Question

Quand avez-vous déjà appliqué directement les concepts de programmation dynamique pour résoudre un problème sur le terrain ? Il est parfois difficile de savoir comment l’appliquer lorsqu’on l’utilise pour résoudre une instance inventée du problème de knapsack .

Answer 1

Il est probablement beaucoup plus courant d'utiliser la mémorisation pour résoudre des problèmes sur le terrain, car cela s'applique à un ensemble plus large de problèmes. DP n’est vraiment utile que lorsque vous rencontrez beaucoup de sous-problèmes qui se chevauchent, comme dans le calcul des nombres de Fibonacci (méthode difficile) ou des nombres premiers (méthode efficace).

Incidemment, la page à laquelle vous avez accédé a une liste des algorithmes utilisant DP. .