Interval DP

Concepts: pyIntervalDP, pyMatrixChain, pyBurstBalloons

Interval DP is a specialized form of 2D DP where dp[i][j] represents 'the optimal cost for the subproblem over the interval [i, j].' The key insight: the optimal answer for a large interval is built from optimal answers for smaller intervals. You always iterate by increasing interval length. This is the opposite of grid DP (which fills row by row). The subproblems are not prefixes; they are intervals. Matrix chain multiplication and burst balloons are the canonical examples. Burst Balloons (LeetCode 312) Given balloons with values nums[], burst them one by one. Bursting balloon k between balloons i and j (inclusive) gives nums[i-1] * nums[k] * nums[j+1] coins. Maximize total coins. The trick: think of the last balloon to burst in interval [i,j], not the first. dp[i][j] = max coins from bur