Java | Recursive | Memoization | Divde and conquer | (2 ms) with clear explanation.
class Solution {\n    \n    Integer[][] dp ;\n    \n    public int minScoreTriangulation(int[] A) {\n        dp= new Integer[A.length][A.length];\n        retur
class Solution {\n    \n    Integer[][] dp ;\n    \n    public int minScoreTriangulation(int[] A) {\n        dp= new Integer[A.length][A.length];\n        return helper(A, 0, A.length-1);\n    }\n    \n    private int helper(int[] nums, int left, int right){\n        \n        // base condition when we have sides less than three. \n        if(left+2>right) return 0;\n      \n        if(dp[left][right]!=null) return dp[left][right];\n        \n        int val=Integer.MAX_VALUE;\n        \n        // The main intuition is to take first and last values as the base \n        //and try all other indices to form a triangle.\n        // Once the traingle is formed with the first, index, left ,\n        //calculate the cost and split the remaining into left and right sub parts  \n        //calculate those left and right recursively.\n        \n        for(int i=left+1; i<right; i++){\n            int leftSum = helper(nums, left, i);\n            int rightSum = helper(nums, i, right);\n            int current = nums[i]*nums[left]*nums[right];\n            val=Math.min(val, current+leftSum + rightSum);\n        }\n        \n        return dp[left][right]=val;\n    }    \n}
[]