Dynamic Programming21 sections · 916 units
Open in Course

Vocabulary - Interval

Range definition

An interval [i,j][i,j] is a contiguous subarray from index i to index j, inclusive. The length is j. I + 11. In interval DP, you typically iterate by length.

First solve all intervals of length 11(base cases), then length 22, then length 33, up to the full array. The answer you want is usually dp[0][n1]dp[0][n-1] or dp[1][n]dp[1][n], depending on whether you use 00-indexed or 11-indexed arrays.