##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Polygon DP
Triangulate a convex polygon to find the lowest sum of triangle scores. Score of triangle = product of vertices. = min cost to triangulate the polygon formed by vertices to .
Transition: pick a vertex between and to form triangle . Cost = . This is Matrix Chain in disguise! The "matrices" are edges, and triangles are the "multiplications".
