Interval DP

Concept

Interval DP solves problems defined over contiguous subarrays (intervals). dp[i][j] represents the answer for the subarray from index i to j. Build solutions from smaller intervals to larger ones. At each step, consider choosing the left or right endpoint and combine with the solution of the remaining interval.

When to Use

• ▸Problems on contiguous subarrays where you pick from ends
• ▸Matrix chain multiplication
• ▸Optimal game strategy (two players picking from ends)
• ▸Merging stones, balloon bursting, palindrome problems

Intuition

Start with intervals of size 1 (base cases). Then solve size 2, size 3, and so on. For each interval [i, j], try all possible 'splits' or 'choices' and pick the optimal one. Think of a game where two players take turns picking from the left or right end of an array — interval DP models all possible game states. The key insight: the answer for [i, j] depends only on smaller intervals within it.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> dp(5005, vector<int>(5005, 0));

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
        dp[i+1][i+1] = v[i];
    }

    for(int size = 2; size <= n; size++){
        for(int i = 1; i <= n-size+1; i++){
            int j = i+size-1;

            int D = abs(v[i-1] - v[j-1]);

            int Left = v[i-1] + D + dp[i+1][j];
            int Right = v[j-1] + D + dp[i][j-1];

            dp[i][j] = max(Left, Right);
        }
    }

    cout << dp[1][n];
    return 0;
}

// Sample Input:
// 5
// 2 1 4 3 5
//
// Sample Output:
// 27