Marvelous memoization :)
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst come up with a backtracking solution trying all possible combinations then later 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst come up with a backtracking solution trying all possible combinations then later optimize using 2d array to avoid repeatitive calculations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCome up with a backtracking soln,  take a pen and paper and draw the tree diagram like this.\n\nEg arr=[1,2,3,4,5] answer=38\n![WhatsApp Image 2024-12-03 at 20.24.52.jpeg](https://assets.leetcode.com/users/images/491af1c3-07d4-4fa9-9082-6c0aad7e5bda_1733237914.9804928.jpeg)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N^3)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N^2)\n# Code\n```java []\nclass Solution {\n    public int matrixChainMul(int[] values,int start,int end,int[][] dp){\n        if(start+1==end){\n            return 0;\n        }\n        if(dp[start][end]!=0){\n            return dp[start][end];\n        }\n        int res=Integer.MAX_VALUE;\n        for(int i=start+1;i<end;i++){\n            int left=matrixChainMul(values,start,i,dp);\n            int right=matrixChainMul(values,i,end,dp);\n            int cur=values[start]*values[i]*values[end];\n            res=Math.min(res,left+right+cur);\n        }\n        dp[start][end]=res;\n        return res;\n    }\n    public int minScoreTriangulation(int[] values) {\n        int[][] dp=new int[values.length][values.length];\n        return matrixChainMul(values,0,values.length-1,dp);\n    }\n}\n```
['Dynamic Programming', 'Backtracking', 'Java']