Easy C++ Solution using Memoization
\n# Approach\nThe problem involves finding the minimum score for triangulating a polygon formed by the given values. Each value represents the vertices of the p
\n# Approach\nThe problem involves finding the minimum score for triangulating a polygon formed by the given values. Each value represents the vertices of the polygon.\n\nDefine a helper function solve that takes the vector of values, the indices i and j representing the range of values to consider, and the memoization array dp as parameters.\n\nIn the solve function, check the base case where i+1==j. If this condition is true, it means there are only two vertices, and no triangle can be formed. Return 0 in this case.\n\nCheck if the result for the current range i to j is already computed and stored in the memoization array dp. If it is, return the precomputed result dp[i][j].\n\nInitialize a variable ans with a large value (INT_MAX), which will be used to store the minimum score for triangulation.\n\nIterate from k=i+1 to k<j to find the optimal split point for triangulation. Calculate the score for the current split point by multiplying values[i], values[j], and values[k] and adding it to the scores of triangulating the two resulting sub-polygons (solve(values, i, k, dp) and solve(values, k, j, dp)).\n\nUpdate ans with the minimum score found among all the split points.\n\nStore the computed minimum score ans in the memoization array dp[i][j] for future reference.\n\nReturn the minimum score for triangulating the given range i to j.\n\nIn the minScoreTriangulation function, initialize the memoization array dp with -1 values.\n\nCall the solve function with the initial range from 0 to n-1, where n is the size of the values vector.\n\nReturn the result obtained from the solve function.\n\nThis approach utilizes memoization to avoid redundant calculations and optimize the solution. It breaks down the problem into smaller subproblems and calculates the minimum score for each subproblem. The minimum score for the overall problem is obtained from the results of these subproblems.\n<!-- Describe your approach to solving the problem. -->\n\nr space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nint solve(vector<int>& values,int i ,int j ,vector<vector<int>>&dp)\n{\n    // BASE CASE CHECK IF THE FIRST ELEMENT AND LAST ELEMENT ARE TOGETHER OR NOT \n    if(i+1==j)\n    {\n        return 0;\n    }\n    if(dp[i][j]!=-1)\n       return dp[i][j];\n    int ans = INT_MAX;\n    for(int k=i+1;k<j;k++)\n    {\n        ans = min(ans , values[i]*values[j]*values[k]+solve(values,i,k,dp)+solve(values, k, j , dp));\n    }\n    dp[i][j]=ans;\n    return dp[i][j];\n\n}\n    int minScoreTriangulation(vector<int>& values)\n    {\n        int n = values.size();\n        vector<vector<int>>dp(n,vector<int>(n,-1));\n        return solve(values,0,n-1,dp); \n    }\n};\n```
['Dynamic Programming', 'C++']