C++ Aditya Verma's Approach ✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \n- Matrix Chain Multiplication [M C M]\n\n# Approach\n Describe your approach to solving
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Matrix Chain Multiplication [M C M]\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- First initialize the dynamic programming array \'dp\' with -1. This is done to indicate that a particular subproblem has not been solved yet. It is initialized to -1 since the minimum possible value is always non-negative, and any valid computed result will be greater than or equal to 0.\n\n- The solve() first checks for the base case where the range of indices is less than 2. If the range i >= j, it returns 0 since there are no triangles to be formed.\n\n- It further checks if the subproblem has already been solved by checking if dp[i][j] is not equal to -1. If the value is already computed, it returns the precomputed value.\n\n- If the subproblem has not been solved before, the function iterates over all possible indices k such that i <= k < j.\n\n- It then recursively calls the solve function on the two subproblems i-k and k+1-j and calculates the temporary answer by adding the two subproblems\' answers and the score of the current triangle formed by the vertices i-1, j, and k. The score of the triangle is calculated by multiplying the values at the three vertices.\n\n- Finally, it returns the minimum value of all possible temporary answers and stores it in the dp array.\n\n- solve() memoizes the results by storing the minimum value of each subproblem in the dp array. By storing the already computed results, it avoids the repeated computation of subproblems, reducing the time complexity of the algorithm.\n\n# Complexity\n- Time complexity: O(n^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int dp[102][102];\n\n    int solve(vector <int> &values, int i, int j)\n    {\n        if(i >= j)\n            return 0;\n\n        if(dp[i][j] != -1)\n            return dp[i][j];\n\n        int mini = INT_MAX;\n\n        for(int k = i; k < j; k++)\n        {\n            int tempAns = solve(values, i, k) + solve(values, k+1, j) + values[i-1] * values[j] * values[k];\n            mini = min(mini, tempAns);\n        }  \n\n        return dp[i][j] = mini;      \n    }\n\n    int minScoreTriangulation(vector<int>& values) \n    {\n        int n = values.size();\n        memset(dp, -1, sizeof(dp));\n        return solve(values, 1, n-1);\n    }\n};\n```
['C++']