Interval and State-Machine DP
Interval DP (matrix chain, burst balloons shape) and state-machine DP (stock trading variants). Code stems are Python.
Question Bank
Hard
Python
interval-dp
state-machine
dynamic-programming
algorithms
892 views
6
Implement max_coins(nums) (LeetCode 312 'Burst Balloons'). After bursting i, you collect nums[left] * nums[i] * nums[right] where left / right are the nearest remaining neighbors.
Examples
Example 1:
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation: Pad to [1, 3, 1, 5, 8, 1]. dp[i][j] = max coins from bursting everything strictly between i and j. Pick the LAST balloon k to burst, contributing nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]. O(n^3).4 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium