C++ RECURSION | MEMOIZATION | CATALAN NUMBERS
Simple Recursive Solution with Memoization\n```\nclass Solution {\npublic:\n    vector> dp;\n    int fun(int i,int j,vector &arr){\n        //Base case \n      
**Simple Recursive Solution with Memoization**\n```\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int fun(int i,int j,vector<int> &arr){\n        //Base case \n        if(j - i <= 1) return 0;\n        if(j - i == 2) return arr[i]*arr[i+1]*arr[i+2];\n        if(dp[i][j] != -1) return dp[i][j];\n        int mini = INT_MAX;\n        for(int part = i+1;part < j;part++){\n            //Now i - part - j creates a triangle \n            int l = fun(i,part,arr);\n            int r = fun(part,j,arr);\n            \n            int ans = arr[i]*arr[j]*arr[part] + l + r;\n            mini = min(mini, ans);\n        }\n        return dp[i][j] = mini;\n    }\n    \n    int minScoreTriangulation(vector<int>& arr) {\n        int n = arr.size();\n        dp = vector<vector<int>> (n,vector<int> (n,-1));\n        return fun(0,n-1,arr); // means we are creating the base of triangle as \n        //the values with vertices 0 and n-1\n        \n    }\n};
['Recursion', 'Memoization']