C++ | Gap Strategy | Matrix Chain Multiplication | (Tabulation+Memoization)
Recursion+Memoization\n\n//TC===>O(n^3)\n//SC====>O(51^2)\nint dp[51][51];\nint solve(int i,int j,vector<int>&values)\n{\n    if(j-i<2)return 0; \n    \n    \n 
**Recursion+Memoization**\n```\n//TC===>O(n^3)\n//SC====>O(51^2)\nint dp[51][51];\nint solve(int i,int j,vector<int>&values)\n{\n    if(j-i<2)return 0; \n    \n    \n    if(dp[i][j]!=-1)return dp[i][j];\n    int ans=INT_MAX;\n     for(int k=i+1;k<j;k++)\n    {\n        int v1=values[i]*values[j]*values[k];\n        int v2=solve(i,k,values)+solve(k,j,values);\n        ans=min(ans,v1+v2);\n    }\n    \n    return dp[i][j]=ans;\n    \n    \n}\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values)\n    {\n       int n=values.size();\n       memset(dp,-1,sizeof(dp));\n       return solve(0,n-1,values);\n        \n    }\n};\n```\n**Tabulation->**\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values)\n    {\n        //TC===>O(N^3)\n        //SC===>O(N^2)\n        int n=values.size();\n        int dp[n][n];\n        memset(dp,0,sizeof(dp));\n        for(int g=2;g<n;g++)\n        {\n            for(int i=0,j=g;j<n;j++,i++)\n            {\n                if(g==2)\n                {\n                    dp[i][j]=(values[i]*values[j]*values[i+1]);\n                }\n                else\n                {\n                    int ans=INT_MAX;\n                    for(int k=i+1;k<j;k++)\n                    {\n                        int v1=values[i]*values[j]*values[k];\n                        int v2=dp[i][k]+dp[k][j];\n                        ans=min(ans,v1+v2);\n                    }\n                    dp[i][j]=ans;\n                }\n            }\n        }\n        \n        \n        return dp[0][n-1]; \n        \n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']