312: Time 90.16%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe idea is to use dynamic programming to solve the problem. We define dp
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe idea is to use dynamic programming to solve the problem. We define dp[i][j] as the maximum coins we can get by bursting all balloons between index i and j (exclusive). We want to compute dp[0][n-1] as the result of the original problem.\n\nTo fill the dp table, we need to find the last balloon to burst. We iterate k from i+1 to j-1, and for each k, we compute the maximum coins we can get by bursting the balloon at k last. This involves the coins we get by bursting the balloon at k, plus the maximum coins we can get for the balloons to the left of k and to the right of k. We add up these three parts to get the maximum coins for subproblems.\n\nThe time complexity of the algorithm is O(n^3), which is acceptable given the constraints of the problem.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        # Add padding to the input array\n        nums = [1] + nums + [1]\n        n = len(nums)\n        # Initialize a dp table to store the maximum coins for subproblems\n        dp = [[0] * n for _ in range(n)]\n        \n        # Iterate the input array in reverse order to fill the dp table\n        for i in range(n-2, -1, -1):\n            for j in range(i+2, n):\n                # Iterate k from i+1 to j-1 to find the last balloon to burst\n                for k in range(i+1, j):\n                    # Compute the maximum coins for subproblems\n                    dp[i][j] = max(dp[i][j], nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])\n        \n        # The result is the maximum coins for the original problem\n        return dp[0][n-1]\n\n```
['Array', 'Dynamic Programming', 'Python', 'Python3']