Comment identifiez-vous un problème comme étant adapté à la programmation dynamique?

J'ai lu récemment sur la programmation dynamique. J'aimerais entendre quelqu'un qui est parti de zéro et qui sait maintenant très bien identifier et résoudre les problèmes de DP. J'ai du mal à identifier ces problèmes comme DP et à élaborer une solution concise.

J'ai traversé la plupart des problèmes de DP débutants et des ressources du MIT, etc.

Je viens d'un milieu physique, et donc, beaucoup de mathématiques. Je trouve des problèmes faciles à repérer bien adaptés aux solutions de programmation récursive / dynamique en trouvant des similitudes avec la preuve par induction .

En preuve par induction vous avez deux parties:

• vous prouvez que si quelque chose est vrai pour l'itération N, c'est aussi vrai pour l'itération N + 1
• vous prouvez que c'est vrai pour l'itération 1

En programmation récursive / programmation dynamique:

• vous identifiez une condition de sortie (par exemple, vous câblez dur la solution pour l'itération 1)
• vous calculez la solution pour l'itération N étant donné la solution pour l'itération N-1

Ainsi, comme d'autres l'ont répondu, c'est une question d'expérience et de choix des indices, mais vous pouvez réutiliser d'autres compétences pour vous guider. Après cela, vous devez toujours avoir les deux parties que j'ai mentionnées: si vous ne le faites pas, cela ne fonctionnera pas.

Par exemple, pour générer toutes les permutations d'un ensemble:

• condition de sortie: si vous n'avez qu'un seul élément, renvoyez-le
• récursivité: les permutations d'un ensemble de N éléments sont les N ensembles de permutations que vous obtenez en choisissant chaque élément et en les combinant avec tous les N-1 ensembles de (nombreuses) permutations du sous-ensemble que vous obtenez en supprimant l'élément.

La plupart des problèmes de programmation dynamique peuvent être résolus via la mémorisation. La mémorisation est normalement à la fois plus intuitive et plus facile à coder. Vous pouvez trouver utile de penser en termes de mémorisation au lieu de DP.

Il est généralement plus facile de deviner si un problème est bien adapté à la mémorisation (les étapes sont les mêmes que la réponse de Slivvz , mais je pense que le changement mental est un peu plus court). Cependant, une fois que vous avez résolu un problème via la mémorisation, vous pouvez examiner comment votre cache de mémos est rempli, puis le remplir dans l'ordre, sans récursivité ... ce qui change votre algorithme en un algorithme de programmation dynamique.

TL; DR; version: Vous trouverez peut-être plus facile de comprendre la programmation dynamique en termes de mémorisation.

Voir aussi StackOverflow: programmation dynamique et mémorisation: approches ascendantes vs descendantes .

La programmation dynamique concerne par définition deux choses:

1. Sous-structure optimale
   Des solutions plus grandes peuvent être dérivées de solutions plus petites; la résolution n'est pas bidirectionnelle.

2. Sous-problèmes qui se chevauchent
   Les petites solutions seront réutilisées plusieurs fois. Si les sous-problèmes ne se chevauchent pas du tout, alors vous ne bénéficiez pas de DP / mémoisation; ce que vous avez, c'est de diviser pour mieux régner .

L'approche générale des problèmes de DP est la suivante:

• Écrivez une version récursive ou itérative naïve qui fonctionne.

• Notez que la fonction effectue un travail redondant.

• Trouvez un moyen d'éviter de faire ce travail redondant, souvent par mémoisation.

Je n'avais jamais implémenté un seul solveur de programmation dynamique - mes antécédents en mathématiques appliquées / physique / informatique numérique, pas en CS - jusqu'à il y a quelques années, lorsque j'ai commencé à résoudre des problèmes liés au projet Euler . Les problèmes solubles dans le DP là-bas (par exemple 76 , 158 , 161 , 242, mais il y en a beaucoup d'autres) s'est avéré être à peu près mon genre préféré. Vous êtes certainement mieux à même de repérer quand ce sera une technique utile: recherchez essentiellement des choses qui semblent pouvoir être résolues par une sorte d'approche récursive, diviser pour mieux régner, où il est également possible de dompter l'explosion de voies nécessitant à explorer en reconnaissant les sous-problèmes récurrents et en réutilisant les résultats précédemment calculés; être en mesure d'identifier le vecteur d'état minimal à mémoriser - et sur quelle "histoire" non pertinente peut être effacée - est l'étape cruciale.