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)