exercice de programmation dynamique sur les cordes de coupe

J'ai travaillé sur le problème suivant de ce livre .

Un certain langage de traitement de chaîne offre une opération primitive qui divise une chaîne en deux parties. Comme cette opération implique la copie de la chaîne d'origine, il faut n unités de temps pour une chaîne de longueur n, quel que soit l'emplacement de la coupe. Supposons maintenant que vous souhaitiez casser une chaîne en plusieurs morceaux. L'ordre dans lequel les pauses sont effectuées peut affecter la durée totale de fonctionnement. Par exemple, si vous voulez couper une chaîne de 20 caractères aux positions $3$ et , effectuer la première coupe à la position entraîne un coût total de , tandis que la position 10 commence d'abord par un meilleur coût de .3 20 + 17 = 37 20 + 10 = $10$$3$$20 + 17 = 37$$20 + 10 = 30$

J'ai besoin d'un algorithme de programmation dynamique qui, compte tenu de coupes, trouve le coût minimum de coupe d'une chaîne en pièces.m + $m$$m +1$

L'idée de base est: Essayez toutes les positions de coupe en premier choix, résolvez les pièces respectives de manière récursive, ajoutez le coût et choisissez le minimum.

En formule:

$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\ &\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' > c\}) \end{align}\right] &, \text{ else} \end{cases}$

Notez que l'application de la mémoisation à cette récursivité permet d'économiser du travail car la commutation de l'ordre de toute paire de coupes successivement appliquée entraîne la résolution des trois mêmes sous-problèmes.

C'est toujours une bonne idée de trouver d'abord un algorithme récursif, puis de le transformer en table.

1. $f(C,n)$
2. $~~$si (C = ) retourne 0;$\emptyset$
3. $~~$autre
4. $~~~~$opt = infini;
5. $~~~~$pour chaque do$c\in C$
6. $~~~~~~D=\{d\in C:d<c\}$
7. $~~~~~~E=\{e-c:e\in D,e>c\}$
8. $~~~~~~opt = min\{opt,f(D,c)+f(E,n-c)\}$
9. $~~~~$retour ;$opt+n$

Vous pouvez donc vous demander: n'y a-t-il pas trop de sous-ensembles de C à mettre dans une table? Notez que seuls des sous-ensembles «consécutifs» sont nécessaires. Et il n'y a que $n \choose 2$$E$$f$

Ceci est très similaire à Quicksort sur un multiset; il est optimal lorsque le point de coupe est le plus proche du milieu, puis nous récursions.

$s_k$