EASY MCM C++ IMPLEMENTATION | SHORT AND COMMENTED CODE
Intuition\n Describe your first thoughts on how to solve this problem. \nJust basic MCM (Matrix chain multiplication) concept implementation.\n\n\n# Complexity\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nJust basic MCM (Matrix chain multiplication) concept implementation.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n     O(N*N*N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n     O(N*N) + O(N)\n# Code\n```\nclass Solution {\npublic:\n    int lol(vector<int>& arr, int i, int j, vector<vector<int>>& dp){\n        // base case\n        if(i == j) return 0;\n\n        if(dp[i][j]!=-1) return dp[i][j];\n\n        int mini = INT_MAX;\n\n        // MCM partitions\n        for(int k = i; k<= j-1; k++){\n            int ans = lol(arr,i,k,dp) + lol(arr,k+1,j,dp) + arr[i-1]*arr[k]*arr[j];\n            mini = min(mini,ans);\n        }\n        return dp[i][j]=mini;\n    }\n    int minScoreTriangulation(vector<int>& arr) {\n        int n=arr.size();\n        int i=1;\n        int j=n-1;\n        vector<vector<int>> dp(n,vector<int>(n,-1));\n\n        return lol(arr,i,j,dp);\n    }\n};\n```
['Array', 'Dynamic Programming', 'C++']