DEV Community

Dev Cookies
Dev Cookies

Posted on

📝 Blog 7: DP on Intervals 🧩

(Mastering Range-Based Dynamic Programming)

🔍 Why DP on Intervals?

Most DP problems we’ve seen so far focus on linear sequences (arrays, strings, grids). But there’s a special class of problems where the answer for a range [i…j] depends on smaller sub-ranges inside it.

This leads us to DP on Intervals, where we split problems into sub-intervals and build solutions bottom-up or with memoized recursion.

Common signs you’re facing an Interval DP problem:

  • The problem asks for minimum/maximum cost to split or merge intervals.
  • You need to partition a string/array into valid groups.
  • Choices depend on a subarray or substring segment.

⚡ Core Template of Interval DP 

for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        // dp[i][j] = best answer for interval [i...j]
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,j));
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
  • len = current interval length.
  • i, j = current interval boundaries.
  • k = possible partition point inside [i, j].

🏆 Classic Problems

1️⃣ Matrix Chain Multiplication

📌 Problem: Find the minimum cost of multiplying a chain of matrices.

  • Order matters; multiplying in different sequences costs differently. 
class MatrixChain {
    public int matrixChainOrder(int[] dims) {
        int n = dims.length;
        int[][] dp = new int[n][n];

        for (int len = 2; len < n; len++) { 
            for (int i = 1; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[1][n-1];
    }
}
Enter fullscreen mode Exit fullscreen mode

2️⃣ Burst Balloons 🎈

📌 Problem: Given balloons with values, maximize coins obtained by choosing order of bursting.

class BurstBalloons {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n+2];
        System.arraycopy(nums, 0, arr, 1, n);
        arr[0] = arr[n+1] = 1;

        int[][] dp = new int[n+2][n+2];

        for (int len = 1; len <= n; len++) {
            for (int left = 1; left <= n-len+1; left++) {
                int right = left + len - 1;
                for (int k = left; k <= right; k++) {
                    dp[left][right] = Math.max(dp[left][right],
                        arr[left-1] * arr[k] * arr[right+1] +
                        dp[left][k-1] + dp[k+1][right]);
                }
            }
        }
        return dp[1][n];
    }
}
Enter fullscreen mode Exit fullscreen mode

3️⃣ Palindrome Partitioning (Min Cuts)

📌 Problem: Split string into minimum cuts so each part is a palindrome.

class PalindromePartition {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j-i < 2 || isPal[i+1][j-1])) {
                    isPal[i][j] = true;
                }
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPal[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = i;
                for (int j = 0; j < i; j++) {
                    if (isPal[j+1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        return dp[n-1];
    }
}
Enter fullscreen mode Exit fullscreen mode

4️⃣ Optimal BST (Binary Search Tree)

📌 Problem: Build a BST from sorted keys that minimizes search cost (given frequencies).

class OptimalBST {
    public int optimalBST(int[] keys, int[] freq) {
        int n = keys.length;
        int[][] dp = new int[n][n];
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + freq[i];

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int r = i; r <= j; r++) {
                    int left = (r > i) ? dp[i][r-1] : 0;
                    int right = (r < j) ? dp[r+1][j] : 0;
                    int sum = prefix[j+1] - prefix[i];
                    dp[i][j] = Math.min(dp[i][j], left + right + sum);
                }
            }
        }
        return dp[0][n-1];
    }
}
Enter fullscreen mode Exit fullscreen mode

🔑 Key Insights

  • Always think about subintervals → [i, j].
  • Check if splitting at k inside [i, j] leads to smaller subproblems.
  • Use bottom-up with increasing interval size (len).
  • Precompute things like palindrome checks or prefix sums to avoid recomputation.

🎯 Real-Life Applications

  • Compilers → parsing and optimal parenthesization.
  • Database query optimization → join ordering.
  • String processing → cutting into valid segments.
  • Game theory → optimal play in ranges.

👉 Nitesh, this was Blog 7: DP on Intervals. Would you like me to next expand on Blog 8: DP on Trees & Graphs 🌳, or do you want me to add more problems with snippets under Interval DP first?

Top comments (0)