Matrix chain multiplication explained for beginners :)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nA famous DP problem is the MCM (matrix chain multiplication) problem, which we will f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nA famous DP problem is the MCM (matrix chain multiplication) problem, which we will first describe because it turns out that this problem of bursting balloons just boils down to the solution of that problem.\n\n### Matrix chain multiplication (MCM) problem\n\nGiven matrices such as ABCDEFGH, which all have different dimensions, but can all be multiplied, find the order in which the matrices should be multiplied to minimise the number of computations. We represent the matrices as an array `arr` where `arr[i]` is the `ith` matrix, and the dimensions of the `ith` matrix are `arr[i-1] x arr[i]`.\n\nFor example, suppose `arr = [5, 6, 7, 1, 5, 11]`. This represents the matrices of sizes `5*6, 6*7, 7*1, 1*5, 5*11`. Notice that `arr[0]` does not represent a matrix.\n\nNow, to solve this problem, we can think about the following. Let\'s say I have `ABCDEF` as my matrices. I could do:\n```\n1. A (BCDEF)\n2. (AB) (CDEF)\n3. (ABC) (DEF)\n4. (ABCD) (EF)\n5. (ABCDE) F\n```\n\nOf course, within each of the brackets containing `> 2` matrices, we would need to decide the order to multiply those as well! But if **we use recursion, we can imagine we have a function that already tells us the cost of multiplying those matrices.**\n\nLet this function be `min_cost(int i, int j)`, where `i` and `j` denote the start and end points of the matrices we want to multiply. For example, to find the answer to the whole problem, we `return min_cost(1, nums.size() - 1)` (remembering that index 0 is not a matrix).\n\nLet `arr = [5,6,7,8,9]`. We have for the first recursive call:\n```\n5 6 7 8 9\n  |     |\n  i     j\n```\nIterate through every `k` in the range `[i,j)`. Suppose `k = 2`:\n```\n    k\n    |\n5 6 7 8 9\n  |     |\n  i     j\n```\nOn the left, we are doing the matrix multiplications `(5,6) x (6,7)`, and on the right we do `(7,8) x (8,9)`. We get the costs of the left multiplications by doing `min_cost(i, k)` and the costs of the right multiplication by doing `min_cost(k+1, j)`.\n\nThe cost of the current matrix multiplication will be `nums[i-1] * nums[k] * nums[j]`. This is because upon performing the left and right multiplications we just need to do `(5,7) x (7,9)`, and the cost of this is `5 * 7 * 9`. We repeat this whole procedure for all valid `k` such that `i <= k < j`, and take the minimum cost as our answer.\n\nThe base case is, of course, when `i == j` meaning we have just one matrix. The cost of multiplying a matrix by nothing is `0`.\n\nTo reduce redundant computations, we can use a memoization hashmap which stores the minimum cost of multiplying matrices in the range `[i,j]` (the tuples `(i,j)` are the keys).\n\n### How does this relate to bursting balloons?\n\nTake our array `arr = [5,6,7,8,9]`. Add `1` to either end to account for the `1` balloons, to make it `[1,5,6,7,8,9]`. Suppose we choose to pop `8`, then we are basically multiplying a `(7,8)` matrix with a `(8,9)` matrix, because the coins we gain are `7*8*9` which is precisely the number of operations to multiply those matrices together!\n\nThe only difference is that we are trying to **maximise** the cost whereas in the MCM problem we are **minimising** the cost. \n\n# Complexity\n- Time complexity: $$ O(n^3) $$ because there are $$ O(n^2) $$ subproblems with keys `(i,j)`, and we do $$ O(n) $$ iterations for each subproblem. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$ O(n^2) $$. We have $$ O(n) $$ items on the call stack, and $$ O(n^2) $$ pairs `(i,j)` stored in `memo`.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` cpp []\nclass Solution {\npublic:\n    unordered_map<int, int> memo;\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        return max_gain(nums, 1, nums.size()-1);\n    }\nprivate:\n    int max_gain(vector<int>& nums, int i, int j) {\n        int hash = pair_hash(i,j);\n        if (i == j) {\n            return 0;\n        }\n        if (memo.find(hash) != memo.end()) {\n            return memo[hash];\n        }\n        int max_cost = 0;\n        for (int k = i; k < j; k++) {\n            int cost = (nums[i-1]*nums[k]*nums[j]) + max_gain(nums, i, k) + max_gain(nums, k+1, j);\n            max_cost = max(max_cost, cost);\n        }\n        memo[hash] = max_cost;\n        return max_cost;\n    }\n    // Cantor pairing function\n    // Bijection from pairs of natural numbers to natural numbers\n    // Guarantees unique hash for pairs\n    int pair_hash(int a, int b) {\n        return ((a + b)*(a + b + 1))/2 + b;\n    }\n};\n```\n``` python []\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n\n        nums.insert(0,1)\n        nums.append(1)\n\n        def recursive(i, j, memo):\n            if i == j:\n                return 0\n            if (i,j) in memo:\n                return memo[(i,j)]\n            max_cost = float(\'-inf\')\n            for k in range(i, j):\n                curr_cost = nums[i-1] * nums[k] * nums[j]\n                left_cost = recursive(i, k, memo)\n                right_cost = recursive(k+1, j, memo)\n                max_cost = max(max_cost, curr_cost + left_cost + right_cost)\n            memo[(i,j)] = max_cost\n            return max_cost\n        \n        memo = {}\n        return recursive(1, len(nums)-1, memo)\n        \n```
['C++', 'Python3']