Java+DP(MCM Variation)+ with Time-Space Analysis
Time Complexity: O(n^3) since we use 2 nested for loops enclosed  with a k(i -> j) loop for every dp[i][j]. \nSpace Complexity: O(n^2) Since, we are using an  n
**Time Complexity:** O(n^3) since we use 2 nested for loops enclosed  with a k(i -> j) loop for every dp[i][j]. \n**Space Complexity:** O(n^2) Since, we are using an  n * n matrix.\n```\nclass Solution {\n    public int minScoreTriangulation(int[] arr) {\n        int[][] dp = new int[arr.length][arr.length];\n        for (int g = 2; g < dp.length; g++) {\n            for (int i = 0, j = g; j < dp[0].length; i++, j++) {\n                 if (g == 2) {\n                    dp[i][j] = arr[i] * arr[i + 1] * arr[i + 2];\n                }\n\n                else {\n                    int min = Integer.MAX_VALUE;\n                    for (int k = i + 1; k <= j - 1; k++) {\n                        int leftpart = dp[i][k];\n                        int rightpart = dp[k][j];\n                        int triangle = arr[i] * arr[j] * arr[k];\n\n                        int total = leftpart + rightpart + triangle;\n                        min=Math.min(min,total);\n                    }\n                     dp[i][j] = min;\n                }\n            }\n           \n        }\n        return dp[0][dp[0].length - 1];  \n    }\n}\n```
['Dynamic Programming', 'Java']