2 Approaches || Recursion+Memoization(Top-Down) & Tabulation(Bottom-Up) || Beats 100%
Intuition: \nThe problem is a classic example of dynamic programming on sequences. The key observation is that any triangulation of the polygon can be divided i
# Intuition: \nThe problem is a classic example of dynamic programming on sequences. The key observation is that any triangulation of the polygon can be divided into smaller triangulations. By solving smaller subproblems and using their results to build up the solution for larger problems, we can efficiently find the minimum score triangulation.\n\n\n# Approach 1: Recursive Approach (Top-Down with Memoization):\n\n- This method involves breaking down the problem into smaller subproblems.\n- For a given range [i,j], the goal is to find the minimum score triangulation of the subpolygon.\n- The base case is when i+1=j, meaning no triangle can be formed.\n- For each potential vertex \uD835\uDC58 between i and j, compute the cost of the triangulation that includes triangle (i,k,j) and recursively solve the subproblems [i,k] and [k,j].\n- Use memoization to store results of subproblems to avoid redundant calculations.\n\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 {\nprivate: \n    int solveMem(vector<int> &values,int i,int j, vector<vector<int>> &dp)\n    {\n        //Base case\n        if(i+1==j) return 0;\n\n        if(dp[i][j]!=-1) return dp[i][j];\n\n        int ans=INT_MAX;\n\n        for(int k=i+1;k<j;k++)\n        {\n             ans=min(ans,values[i]*values[j]*values[k]+solveMem(values,i,k,dp)+solveMem(values,k,j,dp));\n        }\n        dp[i][j]=ans;\n        return dp[i][j];\n    }\n\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n        int n=values.size();\n\n        vector<vector<int>> dp(n,vector<int> (n,-1));\n        return solveMem(values,0,n-1,dp);\n    }\n};\n```\n\n# Approach 2: Tabulation(Bottom-Up Approach)::\n\n- Use a 2D DP array dp where dp[i][j] represents the minimum score to triangulate the subpolygon from vertex i to vertex j.\n- Initialize dp such that dp[i][i + 1] = 0 because no triangle can be formed with less than 3 vertices.\n- Iterate over all possible subpolygon lengths starting from 2 up to the total number of vertices.\n- For each subpolygon [i,j], compute the minimum score by trying all possible vertices k between i and j and updating dp[i][j] with the minimum value.\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\n# Code\n```\nclass Solution {\nprivate: \n    int solveTab(vector<int> &values)\n    {\n        int n=values.size();\n\n        vector<vector<int>> dp(n,vector<int> (n,0));\n\n\n        for(int i=n-1;i>=0;i--)\n        {\n            for(int j=i+2;j<n;j++)\n            {\n                int ans=INT_MAX;\n                for(int k=i+1;k<j;k++)\n                {\n                ans=min(ans,values[i]*values[j]*values[k]+dp[i][k]+dp[k][j]);\n                }\n                    dp[i][j]=ans;\n            }\n\n        }\n        return dp[0][n-1];\n    }\n\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n         return solveTab(values);\n    }\n};\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/9326e095-db55-47e0-84c8-63273e105c5b_1722878627.159309.jpeg)\n
['Recursion', 'Memoization', 'C++']