C++ | TOP DOWN DP | BOTTOM UP DP
TOP DOWN APPROACH\nTime Complexity -> O(N)\nSpace Complexity -> O (N * N)\n\n\tclass Solution {\n\tpublic:\n    \n    int solveMem(vector &v, int i, int j, vect
**TOP DOWN APPROACH**\n*Time Complexity ->* O(N)\n*Space Complexity ->* O (N * N)\n\n\tclass Solution {\n\tpublic:\n    \n    int solveMem(vector<int> &v, int i, int j, vector<vector<int>> &dp)\n    {\n        // base case\n        if (i+1 == j)\n            return 0;\n        \n        if(dp[i][j] != -1)\n            return dp[i][j];\n        \n        int ans = INT_MAX;\n        for (int k=i+1;k<j;k++)          // We can select any vertices between i+1 and j-1\n        {\n            ans = min(ans, v[i]*v[j]*v[k] + solveMem(v, i, k, dp) + solveMem(v, k, j, dp));\n        }\n        dp[i][j] = ans;\n        return dp[i][j];\n    }\n    \n    int minScoreTriangulation(vector<int>& values) {\n        int n = values.size();\n        vector<vector<int>> dp(n, vector<int> (n, -1));\n        return solveMem(values, 0, n-1, dp);\n\t\t}\n\t};\n\t\n**BOTTOM UP APPROACH**\n*Time Complexity ->* O(N * N * N)\n*Space Complexity ->* O(N *  N)\n\n\tclass Solution {\n\tpublic:\n\t\tint solveTab(vector<int> &v)\n\t\t{\n\t\t\tint n = v.size();\n\t\t\tvector<vector<int>> dp (n, vector<int> (n, 0));\n\n\t\t\tint ans = INT_MAX;\n\n\t\t\tfor (int i=n-1;i>=0;i--)\n\t\t\t{\n\t\t\t\tfor (int j=i+2;j<n;j++)\n\t\t\t\t{\n\t\t\t\t\tint ans = INT_MAX;\n\t\t\t\t\tfor (int k=i+1;k<j;k++)\n\t\t\t\t\t{\n\t\t\t\t\t\tans = min (ans, v[i]*v[j]*v[k] + dp[i][k] + dp[k][j]);\n\t\t\t\t\t}\n\t\t\t\t\tdp[i][j] = ans;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn dp[0][n-1];\n\t\t}\n\n\t\tint minScoreTriangulation(vector<int>& values) {\n\t\t\treturn solveTab(values);\n\t\t}\n\t};
['Dynamic Programming']