Burst Balloons
Partition DP & MCM DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Burst Balloons for Maximum Coins (Partition DP / MCM DP Problem), Arrays, Dynamic Programming, Recursion, Memoization, Tabulation, Partition DP, Time Complexity, Space Complexity, Optimal Substructure, Overlapping Subproblems, Base Cases, Edge Cases, recursion with memoization, tabulation, dynamic programming, Partition DP.
Burst Balloons You are given n balloons, indexed from 0 to n 1. Each balloon is painted with a number on it, represented by an array nums. You are asked to burst all the balloons. If you burst the i th balloon, you will get nums[i 1] nums[i] nums[i + 1] coins. If i 1 or i + 1 goes out of the array's bounds, then treat it as if there is a balloon with a 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely. Input Specification: The input consists of a single line containing N, the number of balloons, followed by N space separated integers representing the nums array. Output Specification: Return a single integer representing the maximum coins you can collect. Constraints: 0 <= n <= 500 0 <= nums[i] <= 100 Sample Test Cases: Example 1: Input: Output: Explanation: First, burst the balloon with value 1. Coins = 3 1 5 = 15. Second, burst the balloon with value 5. Coins = 3 5 8 = 120. Third, burst the balloon with value 3. Coins = 1 3 8 = 24. Fourth, burst the balloon with value 8. Coins = 1 8 1 = 8. Total coins = 15 + 120 + 24 + 8 = 167. Example 2: Input: Output: Explanation: First, burst the balloon with value 1. Coins = 1 1 5 = 5. Second, burst the balloon with value 5. Coins = 1 5 1 = 5. Total coins = 5 + 5 = 10.