EASY  MCM + TABULATION C++ CODE | SHORT & BEATS 90%
\n\n- Time complexity:\n Add your time complexity here, e.g. O(n) \n      O(NNN)\n\n- Space complexity:\n Add your space complexity here, e.g. O(n) \n      O(N*
\n\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)\n# Code\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& arr) {\n        int N=arr.size();\n        vector<vector<int>> dp(N,vector<int>(N,-1));\n    \n        for(int i=1;i<N;i++){\n            dp[i][i]=0;\n        }\n        for(int i=N-1;i>=1;i--){\n            for(int j=i+1;j<N;j++){\n                int mini=INT_MAX;\n                // partioning loop\n                for(int k=i;k<=j-1;k++){\n                    int ans = dp[i][k]+ dp[k+1][j] + arr[i-1]*arr[k]*arr[j];\n                    mini = min(mini,ans);\n                }\n                dp[i][j] = mini;\n            }\n        }\n        return dp[1][N-1];\n    }\n};\n```
['Array', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']