Modèles en programmation dynamique - 2

Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.

Si un problème vous demande de détruire/réduire/fusionner (ou similaire) de manière optimale un tableau, alors vous devriez essayer de le résoudre en utilisant la programmation dynamique sur les sous-segments.

Obtenons dp[l][r] - la réponse optimale pour un sous-segment avec des indices de l à r. Le recalcul de la dynamique dépend fortement de la tâche, mais il existe les idées générales suivantes :

1) Regardez les éléments extrêmes l et r. S'ils correspondent ou se complètent d'une autre manière, il sera très probablement possible de mettre à jour la valeur de dp[l][r] via dp[l+1][r-1]. Sinon via dp[l][r-1] ou dp[l+1[r].

2) Il arrive souvent que le segment [l;r] ne puisse être représenté par une seule construction. Ensuite, il est nécessaire de considérer toutes les sections possibles de ce sous-segment en deux parties, c'est-à-dire de parcourir l'élément k de l à r-1 et de recalculer dp[l][r] via dp[l][k] et dp[ k+1][r] . Dans les sous-segments plus petits, ces sections ont également été triées, par conséquent, en fait, les options pour diviser le sous-segment [l;r] non seulement en deux parties, mais en un nombre quelconque d'entre elles sont prises en compte.
 

Avis de non-responsabilité : la méthode décrite ci-dessous n'est pas universelle, mais elle peut souvent résoudre un problème ou vous aider à trouver la bonne solution.

Si vous avez besoin de vérifier l'existence d'une permutation dans un problème, ou de trouver le nombre de permutations qui correspondent, ou quelque chose de similaire, alors vous devriez envisager d'utiliser la programmation de sous-ensemble dynamique.

Le paramètre principal sera un masque de bits, qui montrera quels éléments ont déjà été inclus dans la permutation, et lesquels ne le sont pas. Un deuxième paramètre est également souvent requis pour indiquer quel élément a été inclus en dernier.

Souvent, les permutations peuvent être vues dans le contexte des chemins dans les graphes. En conséquence, considérons un exemple classique - le problème du chemin hamiltonien.
Un chemin hamiltonien est un chemin simple qui passe par chaque sommet du graphe exactement une fois. Il peut être représenté simplement comme une permutation de longueur n, où n est le nombre de sommets. L'ordre dans cette permutation indiquera l'ordre dans lequel les sommets de ce chemin sont traversés.

Afin de vérifier la présence d'un chemin hamiltonien dans le graphe, commençons la dynamique dp[mask][last] - existe-t-il un chemin simple qui a contourné les sommets marqués par des uns dans le masque de masque et s'est retrouvé au dernier sommet.
Les valeurs initiales seront dp[2ⁱ][i] = vrai, le reste faux, ce qui signifie qu'il y a toujours un chemin vide commençant à l'un des sommets.
Ayant la valeur true dans dp[mask][last] nous ferons des transitions vers l'avant, dans le sens de "prolonger le chemin". C'est-à-dire que nous allons chercher les nombres de sommets qui sont marqués de zéro dans le masque (nous ne les avons pas encore visités en chemin) et en même temps tels qu'il y a une arête du dernier à ce sommet (le chemin doit être prolongé par un bord existant). Autrement dit, nous faisons dp[mask | 2^k][k] = vrai si dp[masque][dernier] = vrai ET masque & 2^k = 0 (le sommet k n'a pas encore été visité) Et il y a une arête last -> k.
En fin de compte, un chemin hamiltonien existe s'il existe une vraie valeur dans dp pour les paramètres du masque de bits tout-un et de tout dernier sommet.