Skip to content
CCC Python Course

Interval DP (O(N^3))

Stage
6
Module
M6.6
Lessons
1

In this module

  • Define a subproblem as a contiguous interval in a sequence.
  • Compute solutions bottom-up by increasing interval length.
  • Optimize interval DP with convex hull or monotonicity pruning when O(n³) is too slow.
  • Recognize problems solvable by splitting an interval at each possible position.

Before this module

M4.11Memoization and introductory dynamic programmingM4.3Prefix sums (1D, 2D, prefix/suffix max)M4.9Two pointers and index pointers

Lessons

  1. 1Interval DP and O(n³) algorithms

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2016 S4
    Combining Riceballs (opens on DMOJ in a new tab) DMOJ

    Fill a table over subarrays, from shorter intervals to longer ones, to combine adjacent groups.

    Why DMOJ: An older interval-DP problem that still makes good practice for this module.