Variant of MATRIX CHAIN MULTIPLICATION | DP | DRY RUN attached
Intuition\nThere are three variable which are used i (start point), j (end point) & k (start -> end). This shows its a variation of MATRIX CHAIN MULTIPLICATION\
# Intuition\nThere are three variable which are used `i` (start point), `j` (end point) & `k` (start -> end). This shows its a variation of `MATRIX CHAIN MULTIPLICATION`\n\n# Dry Run for [3,7,4,5]\n![WhatsApp Image 2024-07-29 at 13.00.38_5500335b.jpg](https://assets.leetcode.com/users/images/2dac5bdb-75ec-4033-949c-ffb098bba161_1722238514.0594773.jpeg)\n\n\n# Complexity\n- Time complexity: `O(n^3)`:\n\n    O(n) possible values for i\n    O(n) possible values for j\n    O(n) iterations for k in each subproblem\n\n- Space complexity: `O(n^2)` (2D array)\n\n# Code\n```\nclass Solution {\n    // variant of MATRIX CHAIN MULTIPLICATION\n    public int minScoreTriangulation(int[] values) {\n        int n = values.length;\n        int[][] dp = new int[n][n];\n\n        Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));\n        return mcm(values, 0, n-1, dp);\n    }\n    public int mcm(int[] values, int i, int j, int[][] dp) {\n        if (i >= j-1) return 0; // no triangle possible with 2 points\n        if (dp[i][j] != -1) return dp[i][j];\n\n        int minScore = Integer.MAX_VALUE;\n\n        for(int k=i+1; k<j; k++) {\n            int score = (values[i] * values[j] * values[k]) // current triangle score\n             + mcm(values, i, k, dp)  // left partition score\n             + mcm(values, k, j, dp); // right partition score\n            \n            minScore = Math.min(minScore, score);\n        }\n        return dp[i][j] = minScore;\n    }\n}\n```
['Array', 'Dynamic Programming', 'Java']