Programmation dynamique de l'apprentissage des algorithmes PHP

Programmation dynamique La programmation est un moyen et une méthode pour résoudre des problèmes d'optimisation. La solution optimale du problème final peut être dérivée des solutions optimales des sous-problèmes précédents.

Quant à l'algorithme de programmation dynamique, je ne l'ai pas appris à fond. Un simple résumé de mon expérience d'apprentissage est le suivant :

Les idées de programmation dynamique intègrent les idées de récursivité et de diviser pour régner. , mais différent de diviser pour régner, dans la résolution par programmation dynamique, la solution optimale de chaque branche dans le processus de résolution sera enregistrée via l'état, économisant ainsi les calculs répétés de nombreuses branches.

Les deux étapes les plus importantes et les plus difficiles de la programmation dynamique consistent à trouver l'état qui décrit le sous-problème et la relation de dérivation entre les états.

Problèmes les plus susceptibles d'utiliser la programmation dynamique : trouver les valeurs maximales et minimales, s'il existe des solutions réalisables et le nombre de solutions réalisables.

Essayons d'abord la question la plus courante, trouver la valeur d'une certaine position dans la séquence de Fibonacci (les étudiants qui ne savent pas, veuillez la rechercher sur Baidu) ?
Application de la méthode diviser pour régner pour résoudre le code

Pendant le processus de résolution diviser pour régner, il y aura de nombreuses opérations répétées. 2 ci-dessous ont été répétés deux fois. Plus la valeur de l'indice est grande, plus elle est répétée.

ok, voyons comment la programmation dynamique peut être optimisée.

Nous définissons un tableau pour enregistrer la valeur de chaque position de Fibonacci, ce qui équivaut à définir un état, la valeur de chaque position est égale au ; somme de ses deux précédentes, ce qui équivaut à une équation de transition d’état.
L'enregistrement de l'état via un tableau est ici une idée d'échange d'espace contre du temps. En fait, c'est très similaire à la conception du cache que nous utilisons dans le développement quotidien.

Résumé La solution de programmation dynamique peut être divisée en 4 étapes :
1. Déterminer le sous-problème à résoudre, c'est-à-dire la définition de l'état.
2. Énumérez l’équation de transition d’état.
3. Initialisez la valeur d'état connue en fonction des conditions données.
4. Résolvez la solution finale au problème.

Résolvons un problème plus intéressant, monter les escaliers :

Ce qui précède est le contenu de la programmation dynamique de l'apprentissage des algorithmes PHP, veuillez prêter attention aux informations plus connexes. contenu du site Web chinois PHP (www.php.cn) !