✅ [C++/Python/Java] 2 Simple Solutions || DP and Recursion || Detailed Explanation
PLEASE UPVOTE if you like \uD83D\uDE01 If you have any question, feel free to ask. \n\n The overall idea is divide and conquer\n\t but we cannot select forward 
**PLEASE UPVOTE if you like** \uD83D\uDE01 **If you have any question, feel free to ask.** \n\n* The overall idea is **divide and conquer**\n\t* but we cannot select forward sequentially, because after bursting a balloon, its left and right sides are connected.\n\t* We first select the last bursted balloon, and then find the entire sequence from back to front one by one. \n\t* **Once we tried a certain balloon as the last one to be bursted, before it is bursted, its left and right sides are not connected until the left side left a single one and the right side left a single one too.** \n\t\t* This is the most important observation to solve this problem.\n\t\t* Before you really understand it, you may not find the correct solution easily.\n\t* We can also modify the code to non-recursive style.\n\n**Python3**\n```\nclass Solution(object):\n    def maxCoins(self, nums):\n        @cache\n        def search(nums):\n            return 0 if len(nums) < 3 else max([search(nums[:i + 1]) + search(nums[i:]) \n\t\t\t        + nums[0] * nums[i] * nums[-1] for i in range(1, len(nums) - 1)])\n        return search(tuple([1] + nums + [1]))\n```\n**Python**\n```\nclass Solution(object):\n    def maxCoins(self, nums):\n        nums = [1] + nums + [1]  # add the dummy head and tail, both are left till end and DO NOT burst them.\n        dp = [[0] * len(nums) for _ in nums]  \n        def search(i, j):\n            if j - i < 2: return 0\n            if dp[i][j] > 0: return dp[i][j] \n            for k in range(i + 1, j):\n                dp[i][j] = max(dp[i][j], search(i, k) + search(k, j) + nums[i] * nums[k] * nums[j])\n            return dp[i][j]\n        return search(0, len(nums) - 1)\n```\n**Python Non-recursive**\n```\nclass Solution(object):\n    def maxCoins(self, nums):\n        nums = [1] + nums + [1]  # add the dummy head and tail, both are left till end and DO NOT burst them.\n        dp = [[0] * len(nums) for _ in nums]\n        for i in range(len(nums) - 3, -1, -1):\n            for j in range(i + 2, len(nums)):\n                dp[i][j] = max([dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j] for k in range(i + 1, j)])\n        return dp[0][len(nums) - 1]\n```\n**C++**\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        nums.push_back(1);\n        nums.insert(nums.begin(), 1);\n        vector<vector<int> > dp(nums.size(), vector<int>(nums.size(), 0));\n        for (int i = nums.size() - 3; i >= 0; i --) {\n            for (int j = i + 2; j < nums.size();j ++) {\n                for (int k = i + 1; k < j; k ++)\n                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);\n            }\n        }\n        return dp[0][nums.size() - 1];\n    }\n};\n```\n**Java**\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int[] dummy_num = new int[nums.length + 2];\n        dummy_num[0] = dummy_num[dummy_num.length - 1] = 1;\n        for(int i = 1;i <= nums.length;i ++)\n            dummy_num[i] = nums[i - 1];\n        int[][] dp = new int[dummy_num.length][dummy_num.length];\n        for (int i = dummy_num.length - 3; i >= 0; i --) {\n            for (int j = i + 2; j < dummy_num.length;j ++) {\n                for (int k = i + 1; k < j; k ++)\n                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + dummy_num[i] * dummy_num[k] * dummy_num[j]);\n            }\n        }\n        return dp[0][dummy_num.length - 1];\n    }\n}\n```\n\n**PLEASE UPVOTE if you like** \uD83D\uDE01 **If you have any question, feel free to ask.**
['C', 'Python', 'Java']