C++ | dynamic programming | Using gap strategy
\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n        int n = values.size();\n        vector<vector<int>> dp(n,vector<int>(
```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n        int n = values.size();\n        vector<vector<int>> dp(n,vector<int>(n,0));\n        for(int g = 0;g<n;g++)\n        {\n            for(int i = 0,j = g;j<n;i++,j++)\n            {\n                if(g==0 || g==1)\n                {\n                    dp[i][j] = 0;\n                }\n                else if(g == 2)\n                {\n                    dp[i][j] = values[i]*values[i+1]*values[j];\n                }\n                else\n                {\n                    int ans = INT_MAX;\n                    for(int k = i+1;k<j;k++)\n                    {\n                        int trai = values[i]*values[j]*values[k];\n                        int pleft = dp[i][k];\n                        int pright = dp[k][j];\n                        int total = trai+pleft+pright;\n                        if(total<ans)\n                            ans = total;\n                    }\n                    dp[i][j]=ans;\n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']