Java Solutions Recursion,Memoization and Bottom up DP
Simple Recusion\n\nclass Solution {\npublic int minScoreTriangulation(int[] values) {\n        int n=values.length-1;\n        return solve(values,0,n);\n    }\
Simple Recusion\n```\nclass Solution {\npublic int minScoreTriangulation(int[] values) {\n        int n=values.length-1;\n        return solve(values,0,n);\n    }\n    private int solve(int[] values,int i,int j){\n        if(i+1==j) return 0;\n        int ans=Integer.MAX_VALUE;\n        for(int k=i+1;k<j;k++){\n            ans=Math.min(ans,values[i]*values[j]*values[k]+solve(values,i,k)+solve(values,k,j));\n        }\n        return ans;\n    }\n}\n```\nRecursion using Memoization\n\n```\npublic int minScoreTriangulation(int[] values) {\n        int n=values.length-1;\n        int[][] dp=new int[n+1][n+1];\n        for(int i=0;i<=n;i++){\n            for(int j=0;j<=n;j++) dp[i][j]=-1;\n        }\n        return solveMem(values,0,n,dp);\n    }\n    private int solveMem(int[] values,int i,int j,int[][] dp){\n        if(i+1==j) return 0;\n        if(dp[i][j]!=-1) return dp[i][j];\n        int ans=Integer.MAX_VALUE;\n        for(int k=i+1;k<j;k++){\n            ans=Math.min(ans,values[i]*values[j]*values[k]+solve(values,i,k,dp)+solve(values,k,j,dp));\n        }\n        dp[i][j]=ans;\n        return dp[i][j];\n    }\n```\nBottom up DP\n\n```\npublic int minScoreTriangulation(int[] values) {\n        int n=values.length;\n        int[][] dp=new int[n][n];\n        for(int len=2;len<=n;len++){\n            for(int i=0;i<n-len;i++){\n                int j=i+len;\n                int ans=Integer.MAX_VALUE;\n                for(int k=i+1;k<j;k++){\n                    ans=Math.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```
['Dynamic Programming', 'Recursion', 'Memoization']