Problem Detail: I’m just curious about the pseudocode (or real source code, doesn’t matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that the recursive version takes exponential time and then they give the code for the dynamic programming approach. I understand how the iterative version (dynamic programming ie. memoization) works. But i just wonder about the recursive version. For the info, the key part in the iterative code is:
$ell$ … left
$r$ … right
$a$ … apex
$T$ … triangulation $T_{ell,r}= min{T_{ell,a} + text{perimeter}_{ell,a,r} + T_{a,r}}$
So how does the recursive function findOT() seem in
pseudocode or one of these languages (C#, Java, C/C++, PHP, Javascript, SML)?
Asked By : Schwammkopf
Answered By : A.Schulz
It’s really hard to say, what kind recursion you mean. There are different variants I can think of. For what you have written, I guess it is something like this.
function findOT(int l,r) if ((r-l)==2) return perimeter(l,l+1,r) min= infinity for a=(l+1)..(r-1) T=findOT(l,a)+perimeter(l,a,r)+findOT(a,r) if T<min then min=T endfor return(min)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6720
