3 Methods || easy to understand || 2D DP
PLEASE READ FULL EXPLANATION AND UPVOTE IF YOU UNDERSTAND THE SOLUTIONS\n# Intuition\nIn the question it is given that the array values is in clockwise directio
PLEASE READ FULL EXPLANATION AND UPVOTE IF YOU UNDERSTAND THE SOLUTIONS\n# Intuition\nIn the question it is given that the array values is in clockwise direction it means first element and last element are adjacent\n\n# Approach\n1. take first = i and last = j index as base\n2. now we have last - first indexes left for making a triangle let it be k\n3. now we have a triangle of i, j, k and other part left from i to k and k to j\n4. so call recursively for i and k as base and k and j as base and add it to i*j*k\n5. return the minimum \n\n# Code\n```\nclass Solution {\npublic:\n    int solve(vector<int> &vec, int i, int j){\n        if(i+1 == j) return 0;\n\n        int ans = INT_MAX;\n        for(int k = i+1; k < j; k++){\n            ans = min(ans, vec[i]*vec[j]*vec[k] + solve(vec,i,k) + solve(vec,k,j));\n        }\n        return ans;\n    }\n    int minScoreTriangulation(vector<int>& values) {\n        return solve(values,0,values.size()-1);\n    }\n};\n```\n# Intuition\nin above solution there is overlapping subproblems to it can be solved by dynamic programming \nin above solution 2 parameters are changing so we need a 2d dp\n\n# Approach top down dp\n1. create a 2d dp array of size n+1*n+1 and initialize with -1\n2. store ans in dp[i][j] and return\n3. after base case check if ans is already stored or not\n4. if stored return ans\n5. else call recursion\n\n# Code\n```\nclass Solution {\npublic:\n    int solve(vector<int> &vec, int i, int j,vector<vector<int>> &dp){\n        if(i+1 == j) return 0;\n\n        if(dp[i][j] != -1) return dp[i][j];\n        int ans = INT_MAX;\n        for(int k = i+1; k < j; k++){\n            ans = min(ans, vec[i]*vec[j]*vec[k] + solve(vec,i,k,dp) + solve(vec,k,j,dp));\n        }\n        dp[i][j] = ans;\n        return dp[i][j];\n    }\n    int minScoreTriangulation(vector<int>& values) {\n        int n = values.size();\n        vector<vector<int>> dp(n+1,vector<int>(n+1,-1));\n        return solve(values,0,n-1,dp);\n    }\n};\n```\n# Approach BOTTOM UP DP\n1. create a 2d dp array of size n*n and initialize with 0\n2. analyse base case \n3. since it is a bottom up approach so we traverse from n-1 to 0 for first point (i) of base\n4. and second point of base we traverse form i+2 to n because i+1 can\'t equal to j for making a base\n5. now from i to j make calculate ans like previous approaches by assuming a third point k\n6. return dp[0][n-1]\n\n# Code\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& values) {\n        int n = values.size();\n        vector<vector<int>> dp(n,vector<int>(n,0));\n\n        for(int i = n-1; i >= 0; i--){\n            for(int j = i+2; j < n; j++){\n                int ans = INT_MAX;\n                for(int k = i+1; k < j; k++){\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        return dp[0][n-1];\n    }\n};\n```
['C++']