dynamic programming - Problem Pattern | Matrix Chain Multiplication ||
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is the child problem of MCM .\n\nProblem Description:\nThe problem involves findin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is the child problem of MCM .\n\nProblem Description:\nThe problem involves finding the minimum score needed to triangulate a convex polygon formed by a sequence of vertices, where each vertex has an associated value. Triangulation refers to partitioning the polygon into non-overlapping triangles by connecting the vertices with edges.\n\n\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n O(n^3)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\n    int t[51][51];\n    int solve(vector<int>& values,int i,int j){\n        if(i >= j) return 0;\n        int mn = INT_MAX;\n        if(t[i][j] != -1) return t[i][j];\n        for(int k = i; k <=j-1; k++){\n            int temp = solve(values,i,k) + solve(values,k+1,j) +( values[i-1] * values[k] * values[j]);\n            if(temp < mn) mn = temp;\n        }\n        return t[i][j] = mn;\n    }\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n        memset(t,-1,sizeof(t));\n        int j = values.size()-1;\n        return solve(values,1,j);\n    }\n};\n```
['Array', 'Dynamic Programming', 'Memoization', 'C++']