[C++] DP Solution (Top-down Approach) | W/ Explanation
We need to find the maximum possible coins we can earn by bursting sll the balloons in the array. \n\n Clearly, the brute force approach would try all possible 
We need to find the maximum possible coins we can earn by bursting sll the balloons in the array. \n\n* Clearly, the brute force approach would try all possible combinations of popping the balloons and sofirst we have n choices to select 1 to burst and then in the next step n-1 choices and so on and in the end we are left with the only balloon.\n* We need to find a way to solve this problem for higher numbers. Intuitively, we would try separate the array by popping a particular balloon first so we\'re left with the left & right parts of that element. So if we have ```nums = [3, 1, 5, 8, 7]``` and we try to pop balloon 4 first, would it make the 2 parts [3, 1] & [8, 7] results independent of each other. We cannot forget while calculating [3,1] that [8,9] exists. Why?\n* Because even if we knew in [3,1] in the correct order, we still dont know the exact right neighbor of these elements, right neighbor could be 8 or 7 depending on which of those 2 is popped first.\n* So we need to find a state of dp that could make these 2 parts independent of each other.\n* So instead guessing which balloon to pop first we guess which balloon to pop last. \n* That is, if ```nums =  [3, 1, 5, 8, 7]```  in this array let\'s say  ```3``` was the last one to be popped and then we would know that the left subarray ```[3, 1]``` would always have it\'s right element as 3 because it\'s the last one to be popped and similarly the right subarray [4, 5] would always know it\'s left element.\n* So we\'re going to define a state of dp in which ```dp[l][r]``` = The max no. of coins that can be earned by popping any of the elements in this range at last. \n* Finally ```dp[1][n-1]``` will be our answer (After adding ```1``` to the beginning and end of the array, so each time we wouldn\'t have to check for an out of bound exception).\n* Now, this problem is similar to Matrix Chain Multiplication because, here the main question is how to chose to place the paranthesis. Suppose we have matrices 1, 2, 3, 4, k is the place where the separating paranthesis is placed. When k = 1 then (1) (2, 3, 4) is how the paranthesis are placed. Therefore cost of multiplying all matrices is cost of multiplying matrices frombeginning to k, + cost of multiplying matrices from k+1 to end + cost of multplying both the matrices together (matrix[beginning to k] * matrix[k+1 to end]).\n* So ```total cost = dp[i][k] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j]```.\n\n**Time Complexity :** O(n^3)\n\n**Space Complexity :** O(n^2)\n\n**Code :**\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) \n    {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        int n = nums.size();\n        \n        vector<vector<int>> dp(n, vector<int>(n, -1));\n        return solve(nums, 1, n-1, dp);\n    }\n    \n    int solve(vector<int>& nums, int l, int r, vector<vector<int>> &dp){\n        if(l >= r) return 0;\n        if(dp[l][r] != -1) return dp[l][r];\n        \n        int ans = 0; \n        \n        for(int i = l; i<r; i++){\n            int temp = solve(nums, l, i, dp) + solve(nums, i+1, r, dp) + nums[l-1]*nums[i]*nums[r];\n            ans = max(ans, temp);\n        }\n        return dp[l][r] = ans;\n    } \n};\n```\n\nIf you like my solution & explanation, please upvote my post :)\n\n
['Dynamic Programming', 'C', 'C++']