Easy Solution With Explanation | BOTTOM UP & TOP BOTTOM | C++
[Please Upvote if it helped you ]\nint the comp function we pass the first and last index (l =0 and r = n-1)\n Now every edge of the polygon will be a side of t
[Please Upvote if it helped you ]\nint the comp function we pass the first and last index (l =0 and r = n-1)\n* Now every edge of the polygon will be a side of the triangles to be made \n* lets take an edge to be made by A[0] ,A[n-1] and a vertex i in between the two\n* By taking i our problem is divided into 2 sub-problems of ( l , i ) & ( i , r ) \n* And for the taken i our ans will  be = A[l]*A[r]*A[i] + ans1+ans2; (ans1 and ans2 are ans of the two sub problems) \n* now we have to select the minimum of these answers and return it\n\nNow for DP we see that our function needs start and end index of the array hence we store it in a 2D matrix\n\nTOP BOTTOM:\n```\nclass Solution {\npublic:\n    int comp(int l,int r,vector<int>& A,vector<vector<int>>&dp){\n        if(dp[l][r]!=0)\n            return dp[l][r];\n        if(r-l<2)\n            return 0;\n        if(r-l==2){\n            dp[l][r]=A[l]*A[l+1]*A[r];\n            return dp[l][r];\n        }\n        int max_ans =INT_MAX/2;\n        for(int i=l+1;i<r;i++){\n            int ans1 = comp(l,i,A,dp);\n            int ans2 = comp(i,r,A,dp);\n            int my = A[l]*A[r]*A[i] + ans1+ans2;\n            max_ans = min(max_ans,my);\n        }\n        dp[l][r]=max_ans;\n        return max_ans;\n    }\n    int minScoreTriangulation(vector<int>& A) {\n        int n =A.size();\n        if(n<3)\n            return 0;\n        vector<vector<int>>dp(n,vector<int>(n,0));\n        return comp(0,n-1,A,dp);\n        \n            \n    }\n};\n```\n\nBOTTOM UP:\n\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& A) {\n        int n = A.size();\n        vector<vector<int>>dp(n,vector<int>(n,INT_MAX));\n        for(int len=1;len<=n;len++){\n            for(int start=0;start+len-1<n;start++){\n                int end = start+len-1;\n                if(len<3){\n                    dp[start][end]=0;\n                    continue;\n                }                \n                for(int mid=start+1;mid<end;mid++){\n                    int pro = A[start]*A[mid]*A[end];\n                    int can_be = dp[start][mid]+dp[mid][end]+pro;\n                    dp[start][end] = min(can_be,dp[start][end]);\n                    \n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n};\n```\n\nSlight Variation\n\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& A) {\n        int n = A.size();\n        vector<vector<int>>dp(n,vector<int>(n,0));\n        for(int len=3;len<=n;len++){\n            for(int start=0;start+len-1<n;start++){\n                int end = start+len-1;\n                dp[start][end] = INT_MAX;\n                for(int mid=start+1;mid<end;mid++){\n                    int pro = A[start]*A[mid]*A[end];\n                    int can_be = dp[start][mid]+dp[mid][end]+pro;\n                    dp[start][end] = min(can_be,dp[start][end]);\n                    \n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n};\n```
[]