approche alternative pour Rod coupe algorithme (récursive)

Question

Dans l'introduction du livre à des algorithmes, l'approche naïve de problème de coupe de la tige de résolution peut être décrit par la récurrence suivante:

Soit q le prix maximum qui peut être obtenu à partir de une tige de longueur n.

Laissez le prix tableau [1..n] stocker les prix donnés. prix [i] est le prix donné pour une tige de longueur i.

rodCut(int n) 
{ 
    initialize q as q=INT_MIN 

    for i=1 to n 
     q=max(q,price[i]+rodCut(n-i)) 

    return q 
} 

si je résous en utilisant l'approche ci-dessous:

rodCutv2(int n) 
{ 
    if(n==0) 
    return 0 

    initialize q = price[n] 

    for i = 1 to n/2 
     q = max(q, rodCutv2(i) + rodCutv2(n-i)) 

    return q 
} 

Cette approche est correcte? Si oui, pourquoi utilisons-nous généralement le premier? Pourquoi est-ce mieux?

NOTE: Je suis juste concerné par l'approche pour résoudre ce problème. Je sais que ce problème présente une substructure optimale et des sous-problèmes qui se chevauchent et peut être résolu efficacement en utilisant une programmation dynamique.

Answer 1

Votre algorithme semble presque correct - vous devez faire attention quand n est impair.

Cependant, il est également exponentiel dans la complexité du temps - vous effectuez deux appels récursifs dans chaque appel à rodCutv2. Le premier algorithme utilise la memoisation (le tableau price), évitant ainsi de calculer plusieurs fois la même chose, et il est donc plus rapide (c'est le temps polynomial).

Editer: En fait, le premier algorithme n'est pas correct! Il ne stocke jamais de valeurs dans prices, mais je soupçonne que c'est juste une faute de frappe et non intentionnelle.

Answer 2

Le problème avec la deuxième version est qu'elle n'utilise pas le tableau des prix. Il n'y a pas de cas de base de la récursion, donc ça ne s'arrêtera jamais. Même si vous ajoutez une condition pour retourner le prix [i] lorsque n == 1, le résultat de la coupe de la barre en morceaux de taille 1 sera toujours retourné.