[Solved]: Minimum weight triangulation

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