116.1 (Approach 1 : recursion) | O( n * m)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem involves bursting balloons strategically to maximize the total coins obtained. The key observation is that the choice of which balloon to
# Intuition\nThe problem involves bursting balloons strategically to maximize the total coins obtained. The key observation is that the choice of which balloon to burst last affects the coins obtained from bursting previous balloons. This suggests a dynamic programming approach where we iterate over all possible balloon ranges and compute the maximum coins for each range.\n\n# Approach\nWe use dynamic programming with memoization to solve this problem efficiently. We define a recursive function `dfs` to explore all possible choices of bursting balloons within a given range `[l, r]`. We then memoize the results of subproblems to avoid redundant computations.\n\n1. We add two dummy balloons with value 1 at the beginning and end of the `nums` array to handle edge cases when bursting balloons at the boundaries.\n\n2. Define a recursive function `dfs(l, r)` to compute the maximum coins obtained by bursting balloons within the range `[l, r]`.\n   \n3. Base cases:\n   - If `l` is greater than `r`, it means the range is empty, so we return 0.\n   - If the result for the range `[l, r]` is already memoized, we return it.\n\n4. Initialize the maximum coins obtained within the range `[l, r]` as 0.\n\n5. Iterate over all possible choices of bursting balloons within the range `[l, r]`:\n   - For each balloon `i` in the range `[l, r]`, compute the coins obtained by bursting `nums[i]` last.\n   - Recursively compute the maximum coins obtained from bursting balloons in the two subranges `[l, i - 1]` and `[i + 1, r]`.\n   - Update the maximum coins for the current range `[l, r]` considering the coins obtained by bursting balloon `i` last.\n\n6. Memoize the result for the range `[l, r]` and return the maximum coins obtained.\n\n7. Call the `dfs` function with the initial range `[1, len(nums) - 2]`, excluding the dummy balloons.\n\n# Complexity\n- Time complexity: \\(O(n^3)\\), where \\(n\\) is the length of the `nums` array. The recursive function explores all possible balloon ranges, and for each range, it iterates over all possible choices of bursting balloons, resulting in a cubic time complexity.\n- Space complexity: \\(O(n^2)\\) for the memoization table `memory`. The table stores the results of subproblems for all possible balloon ranges. Additionally, the recursion stack can go up to \\(O(n)\\) in the worst case when each balloon range is explored recursively.\n- \n\n## Python Solution\n```python\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        # Add dummy balloons with value 1 at the beginning and end of the `nums` array\n        nums = [1] + nums + [1]\n        # Initialize a memoization dictionary to store computed results\n        memory = {}\n\n        # Define a recursive function `dfs` to compute maximum coins within a range [l, r]\n        def dfs(l, r):\n            # Base case: If l > r, return 0\n            if l > r:\n                return 0\n            # If the result for the range [l, r] is memoized, return it\n            if (l, r) in memory:\n                return memory[(l, r)]\n            \n            # Initialize maximum coins within the range [l, r]\n            memory[(l, r)] = 0\n            # Iterate over all possible choices of bursting balloons within the range [l, r]\n            for i in range(l, r + 1):\n                coins = nums[l - 1] * nums[i] * nums[r + 1]\n                coins += dfs(l, i - 1) + dfs(i + 1, r)\n                # Update maximum coins for the current range [l, r]\n                memory[(l, r)] = max(memory[(l, r)], coins)\n            \n            return memory[(l, r)]\n        \n        # Call the dfs function with the initial range [1, len(nums) - 2]\n        return dfs(1, len(nums) - 2)\n```\n\n## C++ Solution\n```cpp\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        // Add dummy balloons with value 1 at the beginning and end of the `nums` array\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n        int n = nums.size();\n        \n        // Initialize a memoization table to store computed results\n        vector<vector<int>> memory(n, vector<int>(n, 0));\n        \n        // Call the dfs function with the initial range [1, n - 2]\n        return dfs(nums, memory, 1, n - 2);\n    }\nprivate:\n    int dfs(vector<int>& nums, vector<vector<int>>& memory, int l, int r) {\n        // Base case: If r - l < 0, return 0\n        if (r - l < 0) {\n            return 0;\n        }\n        \n        // If the result for the range [l, r] is memoized, return it\n        if (memory[l][r] > 0) {\n            return memory[l][r];\n        }\n        \n        // Initialize maximum coins within the range [l, r]\n        int ans = 0;\n        // Iterate over all possible choices of bursting balloons within the range [l, r]\n        for (int i = l; i <= r; i++) {\n            int curr = nums[l - 1] * nums[i] * nums[r + 1];\n            int remaining = dfs(nums, memory, l, i - 1) + dfs(nums, memory, i + 1, r);\n            // Update maximum coins for the current range [l, r]\n            ans = max(ans, curr + remaining);\n        }\n        memory[l][r] = ans;\n        return ans;\n    }\n};\n```\n\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C++', 'Python3']