Chapter 23

Dynamic Programming (Advanced) in

Java
Java Data Structures & Algorithms Series

This chapter covers 2D DP, Interval DP, and String DP — the patterns that appear most frequently
in FAANG interviews and competitive programming. Every problem follows the same 4-step
pipeline from Chapter 22.

1 Pattern 1 — Longest Common Subsequence (LCS)

Problem: Find the length of the longest subsequence common to both strings. Subsequence does
not need to be contiguous.

s1 = "ABCBDAB"
s2 = "BDCABA"
LCS = "BCBA" or "BDAB" → length = 4

The Recurrence

If s1[i] == s2[j] → dp[i][j] = 1 + dp[i-1][j-1] (characters match, extend

LCS)
If s1[i] != s2[j] → dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one char)

// Step 2: Memoization
public static int lcsMemo(String s1, String s2, int i, int j, int[][] memo) {
if (i == 0 || j == 0) return 0;
if (memo[i][j] != -1) return memo[i][j];

if ([Link](i-1) == [Link](j-1))
return memo[i][j] = 1 + lcsMemo(s1, s2, i-1, j-1, memo);
return memo[i][j] = [Link](
lcsMemo(s1, s2, i-1, j, memo), // skip s1[i]
lcsMemo(s1, s2, i, j-1, memo) // skip s2[j]
);
}

// Step 3: Tabulation
public static int lcs(String s1, String s2) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1))
dp[i][j] = 1 + dp[i-1][j-1];
 else
dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}

// Time: O(m×n) | Space: O(m×n)

Print the Actual LCS String (Backtracking)

public static String printLCS(String s1, String s2) {

int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if ([Link](i-1) == [Link](j-1)) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);

// Backtrack to find the actual string

StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if ([Link](i-1) == [Link](j-1)) {
[Link]([Link](i-1)); i--; j--;
} else if (dp[i-1][j] > dp[i][j-1]) i--;
else j--;
}
return [Link]().toString();
}

2 Pattern 2 — Edit Distance (Levenshtein Distance)

Problem: Minimum operations (insert, delete, replace) to convert string s1 to s2.

s1 = "horse" s2 = "ros"
horse → rorse (replace h→r)
rorse → rose (delete r)
rose → ros (delete e)
Answer: 3 operations

The Recurrence

If s1[i] == s2[j] → dp[i][j] = dp[i-1][j-1] (no operation needed)

Else → dp[i][j] = 1 + min(
dp[i-1][j], // delete from s1
dp[i][j-1], // insert into s1
dp[i-1][j-1] // replace in s1
)

public static int editDistance(String s1, String s2) {

int m = [Link](), n = [Link]();
 int[][] dp = new int[m+1][n+1];

for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all chars of s1

for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all chars of s2

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + [Link](dp[i-1][j-1],
[Link](dp[i-1][j], dp[i][j-1]));
}
}
return dp[m][n];
}

// Time: O(m×n) | Space: O(m×n)

Space Optimized to O(n)

public static int editDistanceOptimal(String s1, String s2) {

int m = [Link](), n = [Link]();
int[] prev = new int[n+1], curr = new int[n+1];
for (int j = 0; j <= n; j++) prev[j] = j;

for (int i = 1; i <= m; i++) {

curr[0] = i;
for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1)) curr[j] = prev[j-1];
else curr[j] = 1 + [Link](prev[j-1], [Link](prev[j], curr[j-1]));
}
int[] temp = prev; prev = curr; curr = temp;
}
return prev[n];
}

// Time: O(m×n) | Space: O(n)

3 Pattern 3 — Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest strictly increasing subsequence.

arr = [10, 9, 2, 5, 3, 7, 101, 18]

LIS = [2, 3, 7, 18] OR [2, 5, 7, 101] → length = 4

Method 1 — DP O(n²)

public static int lis(int[] nums) {

int n = [Link];
int[] dp = new int[n];
 [Link](dp, 1); // every element is LIS of length 1 by itself

int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = [Link](dp[i], dp[j] + 1);
}
maxLen = [Link](maxLen, dp[i]);
}
return maxLen;
}

// Time: O(n²) | Space: O(n)

Method 2 — Binary Search O(n log n)

public static int lisOptimal(int[] nums) {

List<Integer> tails = new ArrayList<>();
// tails[i] = smallest tail element of all LIS of length i+1

for (int num : nums) {

int lo = 0, hi = [Link]();
while (lo < hi) {
int mid = (lo + hi) / 2;
if ([Link](mid) < num) lo = mid + 1;
else hi = mid;
}
if (lo == [Link]()) [Link](num); // extend LIS
else [Link](lo, num); // replace with smaller tail
}
return [Link]();
}

// Time: O(n log n) | Space: O(n)

4 Pattern 4 — Unique Paths (2D Grid DP)

Problem: Robot starts at top-left of m×n grid. Can only move right or down. Count unique paths to
bottom-right.

3×3 Grid:
S . .
. . .
. . E

Paths: 6

The Recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1] (came from top OR came from left)

// Tabulation
public static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

for (int i = 1; i < m; i++)

for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];

return dp[m-1][n-1];
}

// Space Optimized to O(n)

public static int uniquePathsOptimal(int m, int n) {
int[] dp = new int[n];
[Link](dp, 1);

for (int i = 1; i < m; i++)

for (int j = 1; j < n; j++)
dp[j] += dp[j-1]; // dp[j] = from top, dp[j-1] = from left

return dp[n-1];
}

// Time: O(m×n) | Space: O(n)

5 Pattern 5 — Minimum Path Sum

Problem: Find path from top-left to bottom-right with minimum sum of values.

Grid:
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

Min path: 1→3→1→1→1 = 7

public static int minPathSum(int[][] grid) {

int m = [Link], n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];

for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];

for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

for (int i = 1; i < m; i++)

for (int j = 1; j < n; j++)
dp[i][j] = grid[i][j] + [Link](dp[i-1][j], dp[i][j-1]);

return dp[m-1][n-1];
}
// Time: O(m×n) | Space: O(m×n)

6 Pattern 6 — Longest Palindromic Subsequence

Problem: Find longest palindromic subsequence in a string.

s = "bbbab"
LPS = "bbbb" → length = 4
💡 Key insight: LPS(s) = LCS(s, reverse(s))

// Using LCS shortcut

public static int longestPalindromicSubseq(String s) {
String rev = new StringBuilder(s).reverse().toString();
return lcs(s, rev); // reuse LCS from Pattern 1!
}

// OR solve directly with interval DP

public static int lpsDirect(String s) {
int n = [Link]();
int[][] dp = new int[n][n];

for (int i = 0; i < n; i++) dp[i][i] = 1; // single char = palindrome of length

1

for (int len = 2; len <= n; len++) {

for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if ([Link](i) == [Link](j))
dp[i][j] = 2 + (len > 2 ? dp[i+1][j-1] : 0);
else
dp[i][j] = [Link](dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}

// Time: O(n²) | Space: O(n²)

7 Pattern 7 — Matrix Chain Multiplication (Interval DP)

Problem: Given matrices, find the minimum number of multiplications to compute their product.
Only parenthesization changes — not the order.

Matrices A(10×30), B(30×5), C(5×60)

(A×B)×C = 10×30×5 + 10×5×60 = 1500 + 3000 = 4500
A×(B×C) = 30×5×60 + 10×30×60 = 9000 + 18000 = 27000
Answer: 4500
public static int matrixChain(int[] dims) {
// dims[i-1] x dims[i] = dimensions of matrix i
int n = [Link] - 1;
int[][] dp = new int[n][n];
// dp[i][j] = min cost to multiply matrices i through j

for (int len = 2; len <= n; len++) {

for (int i = 0; i <= n - len; 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] * dims[k+1] * dims[j+1];
dp[i][j] = [Link](dp[i][j], cost);
}
}
}
return dp[0][n-1];
}

// Time: O(n³) | Space: O(n²)

8 Pattern 8 — Burst Balloons

Problem: Burst all balloons to maximize coins. Bursting balloon i gives nums[i-1] × nums[i] ×
nums[i+1].

nums = [3, 1, 5, 8]
Optimal: burst 1→3×1×5=15, burst 5→3×5×8=120, burst 3→1×3×8=24, burst 8→1×8×1=8
Total: 167

⭐ Key Insight: Think of k as the LAST balloon burst in range (i, j), not the first.
This avoids dependency on already-burst neighbours — the classic interval DP trick.

public static int maxCoins(int[] nums) {

int n = [Link];
int[] arr = new int[n + 2];
arr[0] = arr[n+1] = 1; // boundary balloons of value 1
for (int i = 0; i < n; i++) arr[i+1] = nums[i];

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

// dp[i][j] = max coins from bursting all balloons between i and j (exclusive)

for (int len = 1; len <= n; len++) {

for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = [Link](dp[i][j],
dp[i][k-1] + arr[i-1] * arr[k] * arr[j+1] + dp[k+1][j]);
}
}
}
return dp[1][n];
}

// Time: O(n³) | Space: O(n²)

9 Pattern 9 — Partition Equal Subset Sum

Problem: Can array be partitioned into two subsets with equal sum?

nums = [1, 5, 11, 5]

Partition: [1, 5, 5] and [11] → both sum to 11 → true

public static boolean canPartition(int[] nums) {

int total = 0;
for (int n : nums) total += n;
if (total % 2 != 0) return false; // odd total → impossible

int target = total / 2;

boolean[] dp = new boolean[target + 1];
dp[0] = true; // sum 0 always achievable (empty subset)

for (int num : nums)

// Traverse right to left (0/1 knapsack — use each item once)
for (int j = target; j >= num; j--)
dp[j] = dp[j] || dp[j - num];

return dp[target];
}

// Time: O(n × target) | Space: O(target)

10 LCS Variants — All Derived from LCS

Problem Trick Formula

LCS Direct 2D DP dp[i][j]
Edit Distance Insert/Delete/Replace dp[i][j] = 1 + min(3 ops)
Shortest Common Supersequence SCS = m + n - LCS dp[m][n] = m+n-lcs
Longest Palindromic LPS = LCS(s, rev(s)) Reuse LCS
Subsequence
Count Distinct Subsequences Count ways s2 appears in s1 Modified LCS
Wildcard Matching '?' any char, '*' any seq Modified LCS

11 Full Runnable Java Program

import [Link].*;

public class Chapter23DPAdvanced {

 public static void main(String[] args) {
// LCS
[Link]("LCS: " + lcs("ABCBDAB", "BDCABA")); // 4
[Link]("LCS string: " + printLCS("ABCBDAB","BDCABA")); // BCBA

// Edit Distance
[Link]("Edit Distance: " + editDistance("horse","ros")); // 3

// LIS
int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
[Link]("LIS O(n²): " + lis(arr)); // 4
[Link]("LIS O(nlogn): " + lisOptimal(arr)); // 4

// Unique Paths
[Link]("Unique Paths 3x7: " + uniquePathsOptimal(3,7)); // 28

// Min Path Sum

int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
[Link]("Min Path Sum: " + minPathSum(grid)); // 7

// Longest Palindromic Subsequence

[Link]("LPS 'bbbab': " + lpsDirect("bbbab")); // 4

// Matrix Chain
int[] dims = {10, 30, 5, 60};
[Link]("Matrix Chain: " + matrixChain(dims)); // 4500

// Burst Balloons
int[] balloons = {3, 1, 5, 8};
[Link]("Burst Balloons: " + maxCoins(balloons)); // 167

// Partition Equal Subset

int[] nums = {1, 5, 11, 5};
[Link]("Can Partition: " + canPartition(nums)); // true
}

static int lcs(String s1, String s2) {

int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = [Link](i-1)==[Link](j-1)
? 1+dp[i-1][j-1] : [Link](dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}

static String printLCS(String s1, String s2) {

int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = [Link](i-1)==[Link](j-1)
? 1+dp[i-1][j-1] : [Link](dp[i-1][j], dp[i][j-1]);
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if ([Link](i-1)==[Link](j-1)) { [Link]([Link](i-1)); i--;
j--; }
else if (dp[i-1][j] > dp[i][j-1]) i--; else j--;
}
return [Link]().toString();
}
 static int editDistance(String s1, String s2) {
int m = [Link](), n = [Link]();
int[] prev = new int[n+1], curr = new int[n+1];
for (int j = 0; j <= n; j++) prev[j] = j;
for (int ii = 1; ii <= m; ii++) {
curr[0] = ii;
for (int j = 1; j <= n; j++)
curr[j] = [Link](ii-1)==[Link](j-1) ? prev[j-1]
: 1+[Link](prev[j-1], [Link](prev[j], curr[j-1]));
int[] t = prev; prev = curr; curr = t;
}
return prev[n];
}

static int lis(int[] nums) {

int n = [Link]; int[] dp = new int[n]; [Link](dp,1); int max=1;
for (int i=1;i<n;i++){for(int j=0;j<i;j++) if(nums[j]<nums[i])
dp[i]=[Link](dp[i],dp[j]+1); max=[Link](max,dp[i]);}
return max;
}

static int lisOptimal(int[] nums) {

List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int lo=0, hi=[Link]();
while (lo<hi){int mid=(lo+hi)/2; if([Link](mid)<num) lo=mid+1; else
hi=mid;}
if (lo==[Link]()) [Link](num); else [Link](lo,num);
}
return [Link]();
}

static int uniquePathsOptimal(int m, int n) {

int[] dp = new int[n]; [Link](dp,1);
for (int i=1;i<m;i++) for (int j=1;j<n;j++) dp[j]+=dp[j-1];
return dp[n-1];
}

static int minPathSum(int[][] g) {

int m=[Link], n=g[0].length; int[][] dp=new int[m][n]; dp[0][0]=g[0][0];
for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+g[i][0];
for(int j=1;j<n;j++) dp[0][j]=dp[0][j-1]+g[0][j];
for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[i][j]=g[i][j]+[Link](dp[i-1]
[j],dp[i][j-1]);
return dp[m-1][n-1];
}

static int lpsDirect(String s) {

int n=[Link](); int[][] dp=new int[n][n];
for(int i=0;i<n;i++) dp[i][i]=1;
for(int len=2;len<=n;len++) for(int i=0;i<=n-len;i++){int j=i+len-1; dp[i]
[j]=[Link](i)==[Link](j)?2+(len>2?dp[i+1][j-1]:0):[Link](dp[i+1][j],dp[i][j-
1]);}
return dp[0][n-1];
}

static int matrixChain(int[] dims) {

int n=[Link]-1; int[][] dp=new int[n][n];
for(int len=2;len<=n;len++) for(int i=0;i<=n-len;i++){int j=i+len-1; dp[i]
[j]=Integer.MAX_VALUE; for(int k=i;k<j;k++) dp[i][j]=[Link](dp[i][j],dp[i][k]
+dp[k+1][j]+dims[i]*dims[k+1]*dims[j+1]);}
return dp[0][n-1];
}
 static int maxCoins(int[] nums) {
int n=[Link]; int[] arr=new int[n+2]; arr[0]=arr[n+1]=1;
for(int i=0;i<n;i++) arr[i+1]=nums[i];
int[][] dp=new int[n+2][n+2];
for(int len=1;len<=n;len++) for(int i=1;i<=n-len+1;i++){int j=i+len-1;
for(int k=i;k<=j;k++) dp[i][j]=[Link](dp[i][j],dp[i][k-1]+arr[i-
1]*arr[k]*arr[j+1]+dp[k+1][j]);}
return dp[1][n];
}

static boolean canPartition(int[] nums) {

int total=0; for(int n:nums) total+=n;
if(total%2!=0) return false;
int target=total/2; boolean[] dp=new boolean[target+1]; dp[0]=true;
for(int num:nums) for(int j=target;j>=num;j--) dp[j]=dp[j]||dp[j-num];
return dp[target];
}
}

12 Practice Problems for Chapter 23

Solve in this order:

Difficulty Problem
Medium Longest Common Subsequence (LeetCode #1143)
Medium Edit distance (LeetCode #72)
Medium Longest Increasing Subsequence (LeetCode #300)
Medium Unique paths (LeetCode #62)
Medium Minimum path sum (LeetCode #64)
Medium Partition equal subset sum (LeetCode #416)
Medium Longest palindromic subsequence (LeetCode #516)
Hard Burst balloons (LeetCode #312)
Hard Distinct subsequences (LeetCode #115)
Hard Regular expression matching (LeetCode #10)

13 DP Patterns Master Map

1D DP → Fibonacci, Climbing Stairs, House Robber, Coin Change

↓
2D DP → LCS, Edit Distance, Knapsack, Unique Paths
↓
Interval DP → Matrix Chain, Burst Balloons, Palindrome Partition
↓
DP on Graphs → Dijkstra, Bellman-Ford, Floyd-Warshall

💡 Key Insight: Advanced DP problems all share one secret — think about what the LAST action was.
• In Burst Balloons → which balloon was burst LAST?
• In Matrix Chain → where was the LAST split?
This reversal of thinking is what makes hard DP problems click.

Next is Chapter 24 — Advanced Problem Solving, where you combine multiple DSA techniques
together to solve the hardest interview problems! 🚀