C++ Solution || Gap Strategy with explanation
In order to solve this problem we will use the Gap Strategy of dynamic programming.\n1. In this strategy we use a 2D array of n x n and then we assign some mean
In order to solve this problem we will use the Gap Strategy of dynamic programming.\n1. In this strategy we use a 2D array of n x n and then we assign some meaning to the cells of the 2D array.\n2. Then we fill the matrix diagonally, moving from smaller problems to the bigger problem.\n\n**Approach**\n\n>**->** In the dp, rows will correspond to the first vertex which is fixed (i) and columns correspond to the second vertex which is fixed (j) of the polygon (or sub-polygon).\n**->** So at any cell we store the minimum score of triangulation of the sub-polygon that starts with ith vertex and ends with jth vertex in clockwise direction.\n**->** Now talking of the first relevant diagonal; this diagonal represents the scenario, if there were only one vertex in a sub polygon, it will be zero as no triangulation is possible and therefore no score.\n**->** Second diagonal is also dealt in the same way. As there will be no triangulations possible so the cost will also be zero.\n**->** Moving to the next diagonal; we see that this diagonal represents a sub polygon with three vertices. So it means that the polygon is already triangulated. Therefore this diagonal will store the product of values corresponding to each vertex.\n**->** In the next diagonal, to calculate the minimum score of triangulation of a quadrilateral, we have to consider 2 possibilities.\n**->** And the minimum of both these values will be stored at dp which is the final result for this problem.\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n    int n = values.size();\n    vector<vector<int>> dp(n, vector<int>(n));\n    for(int g = 0; g<n; g++){\n        for(int i=0, j = g; j<n; i++, j++){\n            if(g == 0){\n               dp[i][j] = 0;\n            }\n            else if(g == 1){\n               dp[i][j] = 0;\n            }\n            else if(g == 2){\n               dp[i][j] = values[i]*values[j]*values[i+1];\n            }\n            else{\n               int minval = 1e8;\n               for(int k = i+1; k<=j-1; k++){\n                   int tri = values[i]*values[k]*values[j];\n                   int left = dp[i][k];\n                   int right = dp[k][j];\n                   int total = tri + left + right;\n                   minval = min(minval, total);\n               }\n               dp[i][j] = minval;\n            }\n        }\n    }\n    return dp[0][n-1]; \n    }\n};\n```
['Dynamic Programming', 'C']