Burst Balloons
Learn Burst Balloons (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Maximize Coins from Bursting Balloons in Order Bursting a balloon at position k earns coins[left] * coins[k] * coins[right] , where left/right are the CURRENTLY ADJACENT balloons (after previously burst ones are gone). The trick that makes this DP-friendly: think BACKWARD - instead of "which balloon do I burst first", ask "which balloon do I burst LAST within this range" - that balloon's neighbors at burst time are fixed as the range's boundaries, regardless of what happens inside.
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- Minimum Path Sum
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Longest Common Substring
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Optimal BST
- Diameter (Tree DP)
- Maximum Path Sum (Tree DP)
- Tree Independent Set
- Traveling Salesman Problem
- Assignment Problems
- Counting Numbers (Digit DP)
- Digit Constraints