Dynamic programming - clear solution
Intuition and Algorithm\nThis problem is similar to: https://www.geeksforgeeks.org/minimum-cost-polygon-triangulation/\nWe can solved it with Dynamic programmin
**Intuition and Algorithm**\nThis problem is similar to: https://www.geeksforgeeks.org/minimum-cost-polygon-triangulation/\nWe can solved it with Dynamic programming.\n<code>DP(pos1,pos2)</code> = min cost of triangulation of vertices from pos1 to pos2\n<code>if (pos2-pos1<2) return 0;</code> //its not possible to get any triangle\n<code>else DP(pos1,pos2)= min(DP(pos1,k)+ DP(k,pos2) + Cost(pos1,pos2,k))  ) </code>\nWhere <code>  Cost(pos1,pos2,k)</code> is the cost of choose triangle with vertices <code>(pos1,pos2,k)</code> and <code>k</code> go from <code>pos1+1</code> to <code>pos2-1</code>\n**Approach 1 (Dynamic programming)**\n\n<code>\n\n\tclass Solution {\n\tpublic:\n\t\tint memo[51][51];\n\t\t\n\t\tint dp(int pos1,int pos2, vector<int>&A){\n\t\t\tif(pos2-pos1<=1)return 0;//no triangle\n\t\t\t\n\t\t\tif(memo[pos1][pos2]!=-1)return memo[pos1][pos2];\n\t\t\tint ans=1<<30;//initialize in large number\n\t\t\tfor(int i=pos1+1;i<pos2;i++)\n\t\t\t\tans=min(ans, dp(pos1,i,A) + dp(i,pos2,A) + A[pos1]*A[pos2]*A[i] );\n\t\t\t\n\t\t\t//I will check the triangle with vertices (pos1,pos2,i)\n\t\t\t\n\t\t\tmemo[pos1][pos2]=ans;\n\t\t\treturn ans;\n\t\t}\n\t\t\n\t\tint minScoreTriangulation(vector<int>& A) {\n\t\t\tmemset(memo,-1,sizeof(memo));\n\t\t\treturn dp(0,A.size()-1,A);\n\t\t}\n\t};\n\n</code>\n\n<b>Complexity Analysis </b>\n* Time Complexity: O(n ^3) where n is the length of A \n* Space Complexity: O(n^ 2) where n is the length of A
[]