DYNAMIC

PROGRAMMING
MASTERY GUIDE

Java Edition

Beginner to Advanced · Interview Prep · Competitive Programming

[ Recursion ] [ Memoization ] [ Tabulation ] [ Knapsack ] [ LCS ] [ LIS ] [ Coin Change ] [ Edit Distance ]
Dynamic Programming Mastery Guide — Java A Complete Reference

■ Table of Contents
Chapter 1: Introduction to Dynamic Programming
• What is Dynamic Programming?
• Why DP? Motivation & Need
• Recursion vs Memoization vs Tabulation

Chapter 2: When and How to Use DP

• Identifying DP Problems
• Decision-Making Flowchart

Chapter 3: Types of Dynamic Programming

• 1D DP · 2D DP · Grid DP · Tree DP · Bitmask · Digit DP

Chapter 4: Approaches: Top-Down & Bottom-Up

Chapter 5: Step-by-Step Problem Solving Strategy
Chapter 6: Important DP Problems
• Fibonacci, Climbing Stairs, 0/1 Knapsack
• LCS, LIS, Coin Change, Edit Distance
• Matrix Chain Multiplication, Partition DP

Chapter 7: Visualizations & DP Table Diagrams

Chapter 8: Comparison Tables
Chapter 9: Common Mistakes & Debugging Tips
Chapter 10: Practice Problems
Chapter 11: Bonus: Space Optimization & Interview Tips

© DP Mastery Guide — Java Edition Page 2

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

1
Introduction to Dynamic Programming

1.1 What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them
into simpler overlapping subproblems and storing the results to avoid redundant computation. The key
insight is: solve each subproblem once and remember the answer.

The term was coined by Richard Bellman in the 1950s. 'Programming' here refers to 'planning/tabulation'
— not computer programming. DP is not just a technique; it is a way of thinking about optimization and
counting problems.

■ Tip: Think of DP as smart recursion with a memory (cache). Instead of re-computing the same
values over and over, you store them the first time and look them up later.

1.2 Why is DP Needed? A Motivating Example

Consider computing the 40th Fibonacci number recursively. The naive recursive approach computes F(38)
twice, F(37) three times, and so on — leading to exponential time O(2n). DP fixes this by storing results —
bringing it down to O(n).

◆ Recursion Tree for fib(5) — showing redundant calls

fib(5)
/ \
fib(4) fib(3) ← computed AGAIN
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← redundant!
/ \
fib(2) fib(1)

Without DP: O(2^n) With DP: O(n) ← HUGE difference!

1.3 Key Properties for DP

A problem is suitable for DP if it has both of these properties:

© DP Mastery Guide — Java Edition Page 3

Dynamic Programming Mastery Guide — Java A Complete Reference

Property Description Example

Overlapping The same subproblem is solved multiple

fib(3) computed repeatedly in fib(6)
Subproblems times

Optimal solution is built from optimal Shortest path: if A→B→C is shortest,

Optimal Substructure
solutions of subproblems A→B must also be shortest

1.4 Recursion vs Memoization vs Tabulation

There are three main approaches to solving DP problems. Understanding the difference between them is
essential for mastery.

Approach Strategy Direction Memory Speed Ease

Solve subproblems
Brute Recursion Top-Down O(n) stack Slowest Easy
repeatedly

Memoization O(n) Easy-Me

Recursion + cache results Top-Down Fast
(Top-Down) cache+stack dium

Tabulation
Fill table iteratively Bottom-Up O(n) table Fastest Medium
(Bottom-Up)

Space Optimized Use only last few states Bottom-Up O(1) or O(k) Fastest Harder

1.5 Real-Life Analogies

• Memoization = Sticky notes: You solve a math problem, write the answer on a sticky note. Next
time you need it, you just read the note.
• Tabulation = Filling a spreadsheet: You fill cells from left to right, each cell depending only on
previously filled cells.
• DP = Smart path planning: A GPS doesn't recalculate every possible route each time — it builds on
known shortest distances.

1.6 DP vs Divide and Conquer

Aspect Divide & Conquer Dynamic Programming

Subproblems Independent (no overlap) Overlapping

Examples Merge Sort, Quick Sort Fibonacci, Knapsack

Caching Not needed Essential

© DP Mastery Guide — Java Edition Page 4

Dynamic Programming Mastery Guide — Java A Complete Reference

Aspect Divide & Conquer Dynamic Programming

Efficiency gain From splitting From avoiding recomputation

© DP Mastery Guide — Java Edition Page 5

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

2
When and How to Use DP

2.1 Identifying DP Problems

Not every problem requires DP. Learning to identify DP problems quickly is a crucial competitive
programming and interview skill. Look for these signals:

• The problem asks for the minimum/maximum of something

• The problem asks to count the number of ways to do something
• The problem asks whether something is possible/achievable
• The problem involves making a series of decisions that affect future options
• Brute-force involves trying all subsets, permutations, or recursive branches
• Keywords: optimal, fewest, most, can we achieve, how many ways, longest, shortest

2.2 Decision-Making Flowchart

◆ DP Problem Identification Flowchart

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■ Is the problem about optimization ■
■ or counting? ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
YES NO
■ ■■■■ Use Greedy / Graph / Math
▼
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■ Do subproblems OVERLAP? ■
■ (Same sub-calculation repeats?) ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
YES NO
■ ■■■■ Use Divide & Conquer
▼
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■ Does optimal solution decompose ■
■ into optimal sub-solutions? ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
YES NO

© DP Mastery Guide — Java Edition Page 6

Dynamic Programming Mastery Guide — Java A Complete Reference

■ ■■■■ Backtracking / Search

▼
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■ ■ USE DYNAMIC PROGRAMMING ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

2.3 DP Pattern Recognition Cheat Sheet

Problem Type DP Pattern Classic Examples

Prefix/suffix optimization 1D DP on array Kadane's, LIS

Two sequences
2D DP grid LCS, Edit Distance
comparison

Pick items with

Knapsack DP 0/1 Knapsack, Coin Change
constraints

Path in a grid Grid DP Unique Paths, Min Path Sum

Partition an array/string Interval DP Matrix Chain, Palindrome Partition

Subsets/permutations Bitmask DP TSP, Assignment Problem

Count digits with

Digit DP Count numbers with digit sum
property

Tree structure
Tree DP Diameter, Maximum Independent Set
optimization

© DP Mastery Guide — Java Edition Page 7

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

3
Types of Dynamic Programming

3.1 1D Dynamic Programming

In 1D DP, the state is defined by a single index. We build a 1D array where each cell represents the
answer to a subproblem ending/starting at that index.

• Examples: Fibonacci, Climbing Stairs, House Robber, Kadane's Algorithm

• State: dp[i] = answer considering first i elements

dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k])

3.2 2D Dynamic Programming

2D DP uses a 2D table where the state depends on two parameters — often two indices, or one index plus
a capacity/constraint.

• Examples: 0/1 Knapsack, LCS, Edit Distance, Unique Paths

• State: dp[i][j] = answer considering first i items and capacity/length j

dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

3.3 DP on Grids
Grid DP problems involve navigating a 2D matrix. Movement is typically restricted (e.g., only right and
down), allowing bottom-up filling.

• Examples: Unique Paths, Minimum Path Sum, Dungeon Game

• State: dp[row][col] = best value to reach this cell

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

3.4 DP on Trees
Tree DP is solved using DFS, where each node's answer depends on its children's answers. Common in
tree structure optimization problems.

• Examples: Tree Diameter, Maximum Independent Set on Tree

• State: dp[node][0/1] = answer for subtree rooted at node (included/excluded)

© DP Mastery Guide — Java Edition Page 8

Dynamic Programming Mastery Guide — Java A Complete Reference

3.5 DP on Subsequences
These problems ask about subsequences (not necessarily contiguous) of arrays or strings. Often involve
two-pointer or two-sequence DP.

• Examples: LCS, LIS, Number of Subsequences, Distinct Subsequences

3.6 Bitmask DP (Introduction)

Bitmask DP uses a bitmask (integer) to represent which elements have been selected/visited. Used when
n is small (typically n ≤ 20).

• State: dp[mask][i] = optimal value having visited items in mask, currently at i

• Classic problem: Travelling Salesman Problem (TSP)

■■ Note: Bitmask DP has O(2n × n) complexity — only feasible for n ≤ 20.

3.7 Digit DP (Introduction)

Digit DP counts numbers in a range [L, R] satisfying some digit-related property. It processes the number
digit by digit from left to right.

• State variables: position, tight constraint, carry/sum so far

• Examples: Count numbers with digit sum = k, Count numbers with no consecutive 1s

© DP Mastery Guide — Java Edition Page 9

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

4
Approaches in DP

4.1 Top-Down (Memoization)

Start with the original problem and recursively break it down. Before computing a subproblem, check if it's
already cached. If yes, return cached value. If no, compute and cache it.

◆ Top-Down Memoization Template (Java)

// Memoization Template
int[] memo = new int[n];
[Link](memo, -1); // -1 means not computed yet

int solve(int i) {
if (base_case) return base_value;
if (memo[i] != -1) return memo[i]; // Already solved
memo[i] = /* recurrence relation using recursive calls */;
return memo[i];
}

■ Advantages: Only computes subproblems that are actually needed. Easy to write — just add a
cache to your recursive solution.

■■ Note: Disadvantages: Overhead from recursive calls. Risk of stack overflow for deep recursion.

4.2 Bottom-Up (Tabulation)

Start from the smallest subproblems (base cases) and iteratively build up to the original problem. Fill a DP
table in order such that when you compute dp[i], all smaller subproblems are already solved.

◆ Bottom-Up Tabulation Template (Java)

// Tabulation Template
int[] dp = new int[n + 1];
dp[0] = base_case_0; // Initialize base cases
dp[1] = base_case_1;

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

dp[i] = /* recurrence relation using dp[i-1], dp[i-2], ... */;

© DP Mastery Guide — Java Edition Page 10

Dynamic Programming Mastery Guide — Java A Complete Reference

return dp[n]; // Answer to original problem

■ Advantages: No recursion overhead. Better cache performance. Easier to optimize space.

4.3 Detailed Comparison

Aspect Top-Down (Memoization) Bottom-Up (Tabulation)

Code style Recursive Iterative

Starting point Original problem → subproblems Base cases → original problem

Subproblems
Only needed ones All (even unused ones)
solved

Stack usage O(n) recursion stack O(1) (no stack)

Space
Hard to achieve Easy to reduce to O(1)
optimization

Readability More intuitive Slightly less intuitive

Risk Stack overflow for large n Iteration order must be correct

Best for Unknown/sparse subproblems Known/dense subproblems

Performance Slightly slower (overhead) Slightly faster

4.4 When to Prefer Which Approach

• Prefer Top-Down when: The recurrence is complex, you're prototyping quickly, or only a small
fraction of subproblems are needed.
• Prefer Bottom-Up when: You need space optimization, the subproblem graph is dense, or you want
to avoid stack overflow.
• In interviews: Start with top-down (easier to explain), then convert to bottom-up if asked to optimize.

© DP Mastery Guide — Java Edition Page 11

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

5
Step-by-Step Problem Solving Strategy

Every DP problem can be cracked using this systematic 5-step framework. Mastering this strategy will help
you tackle even unfamiliar problems in interviews.

Step 1: Define the State

What does dp[i] (or dp[i][j]) represent?

• The state must capture all information needed to solve the subproblem
• Be precise: 'dp[i] = maximum profit using first i items'
• A bad state definition leads to incorrect recurrences

Step 2: Identify the Recurrence

How does dp[i] relate to smaller subproblems?

• Express dp[i] as a function of dp[i-1], dp[i-2], etc.

• Consider all possible 'last decisions' made to reach state i
• This is the heart of DP — take your time here

Step 3: Define Base Cases

What are the smallest subproblems you can solve directly?

• Base cases are subproblems with no smaller subproblems

• Typically: dp[0] = 0, dp[1] = 1, or similar
• Wrong base cases → wrong answers for all larger states

Step 4: Determine Iteration Order

In what order should you fill the DP table?

• Each state must be computed only after all states it depends on

• For 1D: usually left-to-right
• For 2D: usually top-to-bottom, left-to-right

Step 5: Identify the Answer

Where in the DP table is the final answer?

• Sometimes it's dp[n], sometimes it's max(dp[0..n])

• Be clear about this before coding

© DP Mastery Guide — Java Edition Page 12

Dynamic Programming Mastery Guide — Java A Complete Reference

• Trace through a small example to verify

5.1 Example: Applying the Framework to Climbing Stairs

◆ Framework Applied: Climbing Stairs

Problem: Count ways to climb n stairs, taking 1 or 2 steps at a time.

Step 1 — State: dp[i] = number of ways to reach step i

Step 2 — Recurrence: dp[i] = dp[i-1] + dp[i-2]
(last step was 1 step: came from i-1)
(last step was 2 steps: came from i-2)
Step 3 — Base cases: dp[0]=1 (1 way: do nothing), dp[1]=1 (1 way: one step)
Step 4 — Order: Fill dp[2], dp[3], ..., dp[n] left to right
Step 5 — Answer: dp[n]

5.2 Space Optimization Techniques

• Rolling array: If dp[i] depends only on dp[i-1] and dp[i-2], keep only 2 variables
• 1D instead of 2D: For knapsack, process capacity in reverse to use 1D array
• Prefix sums: Avoid nested loops by precomputing cumulative sums
• Monotonic deque: Optimize sliding window DP from O(n*k) to O(n)

© DP Mastery Guide — Java Edition Page 13

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

6
Important DP Problems

Problem 1: Fibonacci Number

Difficulty: Easy

Problem Statement
Compute the n-th Fibonacci number. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

Approach 1: Brute Force Recursion

◆ Fibonacci — Brute Force (Java)

// Time: O(2^n) | Space: O(n) stack

public int fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Approach 2: Top-Down (Memoization)

◆ Fibonacci — Memoization (Java)

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

int[] memo = new int[n + 1];
[Link](memo, -1);

public int fibMemo(int n) {

if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}

Approach 3: Bottom-Up (Tabulation)

◆ Fibonacci — Tabulation (Java)

© DP Mastery Guide — Java Edition Page 14

Dynamic Programming Mastery Guide — Java A Complete Reference

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

public int fibTab(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}

Approach 4: Space Optimized

◆ Fibonacci — Space Optimized (Java)

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

public int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}

Complexit
y Time Space

Analysis O(n) O(1) — space optimized

© DP Mastery Guide — Java Edition Page 15

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 2: Climbing Stairs

Difficulty: Easy

Problem Statement
You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways
can you climb to the top?

Key Insight
This is exactly the Fibonacci sequence! dp[n] = dp[n-1] + dp[n-2].

dp[i] = dp[i-1] + dp[i-2]

◆ Climbing Stairs — Space Optimized (Java)

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

public int climbStairs(int n) {
if (n <= 2) return n;
int one = 2, two = 1; // dp[2], dp[1]
for (int i = 3; i <= n; i++) {
int curr = one + two;
two = one;
one = curr;
}
return one;
}

// DP Table for n=5:

// dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8

© DP Mastery Guide — Java Edition Page 16

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 3: 0/1 Knapsack

Difficulty: Medium

Problem Statement
Given n items each with a weight and value, and a knapsack of capacity W, find the maximum value you
can carry. Each item can be taken at most once (0/1 = don't take or take).

State Definition
dp[i][w] = max value using first i items with capacity w

Recurrence Relation
◆ Knapsack Recurrence

If weight[i] > w: dp[i][w] = dp[i-1][w] // Can't include item i

Else: dp[i][w] = max(dp[i-1][w], // Exclude item i
dp[i-1][w-weight[i]] + value[i]) // Include item
i

Tabulation Solution
◆ 0/1 Knapsack — Tabulation (Java)

// Time: O(n*W) | Space: O(n*W)

public int knapsack(int[] weight, int[] value, int W) {
int n = [Link];
int[][] dp = new int[n + 1][W + 1];

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

for (int w = 0; w <= W; w++) {
// Option 1: Don't take item i
dp[i][w] = dp[i-1][w];
// Option 2: Take item i (if it fits)
if (weight[i-1] <= w) {
dp[i][w] = [Link](dp[i][w],
dp[i-1][w - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][W];
}

© DP Mastery Guide — Java Edition Page 17

Dynamic Programming Mastery Guide — Java A Complete Reference

Space-Optimized (1D DP)

◆ 0/1 Knapsack — Space Optimized (Java)

// Time: O(n*W) | Space: O(W)

public int knapsackOptimized(int[] weight, int[] value, int W) {
int n = [Link];
int[] dp = new int[W + 1];

for (int i = 0; i < n; i++) {

// Traverse BACKWARDS to avoid using item i twice
for (int w = W; w >= weight[i]; w--) {
dp[w] = [Link](dp[w], dp[w - weight[i]] + value[i]);
}
}
return dp[W];
}

■■ Note: Key insight: Iterate capacity in REVERSE order in the space-optimized version. This
prevents an item from being selected multiple times.

Complexit
y Time Space

Analysis O(n × W) O(W) — space optimized

© DP Mastery Guide — Java Edition Page 18

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 4: Longest Common Subsequence (LCS)

Difficulty: Medium

Problem Statement
Given two strings s1 and s2, find the length of their longest common subsequence. A subsequence is a
sequence that can be derived by deleting some characters without changing the relative order.

Example: s1 = 'ABCBDAB', s2 = 'BDCAB' → LCS = 'BCAB' (length 4)

State & Recurrence

dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]

◆ LCS Recurrence

If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 // Characters match!

Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // Take best

◆ LCS — Full Solution (Java)

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

public 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] = dp[i-1][j-1] + 1; // Match
} else {
dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]); // No match
}
}
}
return dp[m][n];
}

DP Table Visualization
◆ LCS DP Table — Step-by-Step Fill

s1 = 'ABCB' s2 = 'BCB'

'' B C B
'' [ 0 0 0 0 ]

© DP Mastery Guide — Java Edition Page 19

Dynamic Programming Mastery Guide — Java A Complete Reference

A [ 0 0 0 0 ]
B [ 0 1 1 1 ] ← B matches B
C [ 0 1 2 2 ] ← C matches C
B [ 0 1 2 3 ] ← B matches B → LCS = 3 (BCB)

Complexit
y Time Space

O(n) — space optimized

Analysis O(m × n) with 2 rows

© DP Mastery Guide — Java Edition Page 20

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 5: Longest Increasing Subsequence (LIS)

Difficulty: Medium

Problem Statement
Given an array nums[], find the length of the longest strictly increasing subsequence.

Example: [10, 9, 2, 5, 3, 7, 101, 18] → LIS = [2, 3, 7, 18] (length 4)

DP Approach — O(n²)
dp[i] = length of LIS ending at index i

◆ LIS — O(n²) DP (Java)

// Time: O(n^2) | Space: O(n)

public int lengthOfLIS(int[] nums) {
int n = [Link];
int[] dp = new int[n];
[Link](dp, 1); // Each element alone is LIS of length 1

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

Optimized Approach — O(n log n) with Binary Search

◆ LIS — O(n log n) Optimized (Java)

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

// Maintain 'tails' array: tails[i] = smallest tail of all IS of length i+1
public int lengthOfLISOptimized(int[] nums) {
List<Integer> tails = new ArrayList<>();

for (int num : nums) {

// Binary search for leftmost position >= num
int lo = 0, hi = [Link]();
while (lo < hi) {

© DP Mastery Guide — Java Edition Page 21

Dynamic Programming Mastery Guide — Java A Complete Reference

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 (smaller tail = better)
}
return [Link]();
}

Complexit
y Time Space

Analysis O(n log n) O(n)

© DP Mastery Guide — Java Edition Page 22

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 6: Coin Change

Difficulty: Medium

Problem Statement
Given coin denominations and a target amount, find the minimum number of coins needed to make the
amount. Return -1 if impossible.

Example: coins=[1,5,6,9], amount=11 → Answer: 2 (5+6)

State & Recurrence

dp[i] = min coins needed to make amount i

dp[i] = 1 + min(dp[i - coin]) for each coin ≤ i

◆ Coin Change — Tabulation (Java)

// Time: O(amount * coins) | Space: O(amount)

public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1); // Initialize to 'infinity'
dp[0] = 0; // Base case: 0 coins needed for amount 0

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

for (int coin : coins) {
if (coin <= i) {
dp[i] = [Link](dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}

// DP Table for coins=[1,2,5], amount=5:

// dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=2, dp[5]=1

Complexit
y Time Space

Analysis O(amount × |coins|) O(amount)

© DP Mastery Guide — Java Edition Page 23

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 7: Edit Distance (Levenshtein Distance)

Difficulty: Medium-Hard

Problem Statement
Given two strings word1 and word2, find the minimum number of operations (insert, delete, replace) to
convert word1 to word2.

Example: word1='horse', word2='ros' → 3 operations

State & Recurrence

dp[i][j] = min operations to convert word1[0..i-1] to
word2[0..j-1]

◆ Edit Distance Recurrence

If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] // No operation needed

Else: dp[i][j] = 1 + min(
dp[i-1][j], // Delete from word1
dp[i][j-1], // Insert into word1
dp[i-1][j-1] // Replace
)

◆ Edit Distance — Full Solution (Java)

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

public int minDistance(String word1, String word2) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m + 1][n + 1];

// Base cases
for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all of word1
for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all of word2

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];

© DP Mastery Guide — Java Edition Page 24

Dynamic Programming Mastery Guide — Java A Complete Reference

DP Table Visualization
◆ Edit Distance DP Table

word1='horse' word2='ros'

'' r o s
'' [ 0 1 2 3 ]
h [ 1 1 2 3 ]
o [ 2 2 1 2 ]
r [ 3 2 2 2 ]
s [ 4 3 3 2 ]
e [ 5 4 4 3 ] ← Answer = 3

Complexit
y Time Space

O(n) — space optimized

Analysis O(m × n) with 2 rows

© DP Mastery Guide — Java Edition Page 25

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 8: Matrix Chain Multiplication

Difficulty: Hard

Problem Statement
Given a sequence of matrices, find the minimum number of scalar multiplications needed to compute their
product. The order of multiplication matters for efficiency!

Example: Matrices A(10x30), B(30x5), C(5x60)

• (AB)C: 10*30*5 + 10*5*60 = 1500 + 3000 = 4500

• A(BC): 30*5*60 + 10*30*60 = 9000 + 18000 = 27000
• Best: (AB)C with 4500 multiplications

State & Recurrence (Interval DP)

dp[i][j] = min cost to multiply matrices from index i to j

dp[i][j] = min over all k in [i, j-1] of:

dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]

◆ Matrix Chain Multiplication — Interval DP (Java)

// Time: O(n^3) | Space: O(n^2)

// dims[i] = dimension: matrix i has dims[i-1] rows, dims[i] cols
public int matrixChainOrder(int[] dims) {
int n = [Link] - 1; // number of matrices
int[][] dp = new int[n + 1][n + 1];

// len = chain length (2, 3, ..., 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;
// Try every split point k
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] = [Link](dp[i][j], cost);
}
}
}
return dp[1][n];
}

© DP Mastery Guide — Java Edition Page 26

Dynamic Programming Mastery Guide — Java A Complete Reference

Complexit
y Time Space

Analysis O(n³) O(n²)

© DP Mastery Guide — Java Edition Page 27

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem 9: Partition DP: Palindrome Partitioning

Difficulty: Hard

Problem Statement
Given a string s, partition it such that every substring is a palindrome. Find the minimum number of cuts
needed.

Example: s='aab' → ['aa','b'], 1 cut

Two-Phase DP Solution
◆ Palindrome Partitioning — Minimum Cuts (Java)

// Time: O(n^2) | Space: O(n^2)

public int minCut(String s) {
int n = [Link]();

// Phase 1: Precompute isPalin[i][j]

boolean[][] isPalin = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if ([Link](i) == [Link](j) && (j - i <= 2 || isPalin[i+1][j-1]))
isPalin[i][j] = true;
}
}

// Phase 2: dp[i] = min cuts for s[0..i]

int[] dp = new int[n];
[Link](dp, Integer.MAX_VALUE);

for (int i = 0; i < n; i++) {

if (isPalin[0][i]) {
dp[i] = 0; // Whole s[0..i] is palindrome, no cuts needed
} else {
for (int j = 1; j <= i; j++) {
if (isPalin[j][i]) {
dp[i] = [Link](dp[i], dp[j-1] + 1);
}
}
}
}
return dp[n - 1];
}

© DP Mastery Guide — Java Edition Page 28

Dynamic Programming Mastery Guide — Java A Complete Reference

Complexit
y Time Space

Analysis O(n²) O(n²)

© DP Mastery Guide — Java Edition Page 29

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

7
Visualizations & DP Diagrams

7.1 Recursion Tree vs Memoization

◆ Recursion Tree Comparison: Without vs With Memoization

■■ WITHOUT Memoization (fib(5)) ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

fib(5)
/ \
fib(4) fib(3) ← REDUNDANT
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← MORE REDUNDANCY
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
Calls: 15 Time: O(2^n)

■■ WITH Memoization (fib(5)) ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

fib(5)
/ \
fib(4) [3]✓cached
/ \
fib(3) [2]✓cached
/ \
fib(2) [1]✓cached
/ \
fib(1) fib(0)
Calls: 9 Time: O(n) ← dramatic reduction!

7.2 DP Table Filling: Knapsack Example

◆ 0/1 Knapsack DP Table — Complete Walkthrough

Items: [(weight=2, value=6), (weight=2, value=10), (weight=3, value=12)]

Capacity W = 5

© DP Mastery Guide — Java Edition Page 30

Dynamic Programming Mastery Guide — Java A Complete Reference

dp[i][w] = max value using first i items, capacity w

w=0 w=1 w=2 w=3 w=4 w=5

i=0 [ 0 0 0 0 0 0 ] (no items)
i=1 [ 0 0 6 6 6 6 ] (item1: w=2,v=6)
i=2 [ 0 0 10 10 16 16 ] (item2: w=2,v=10)
i=3 [ 0 0 10 12 16 22 ] (item3: w=3,v=12)
↑
Answer = 22 (item2 + item3)

Traceback: dp[3][5]=22 ← came from dp[2][2]+12 = 10+12

dp[2][2]=10 ← took item2 (w=2, v=10)
Selected items: item2 + item3

7.3 LCS Table Filling Step-by-Step

◆ LCS DP Table — Complete Fill

s1 = 'AGGTAB' s2 = 'GXTXAYB'

Fill Rules:
• If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

'' G X T X A Y B
'' [ 0 0 0 0 0 0 0 0 ]
A [ 0 0 0 0 0 1 1 1 ]
G [ 0 1 1 1 1 1 1 1 ]
G [ 0 1 1 1 1 1 1 1 ]
T [ 0 1 1 2 2 2 2 2 ]
A [ 0 1 1 2 2 3 3 3 ]
B [ 0 1 1 2 2 3 3 4 ] ← LCS length = 4 (GTAB)

7.4 Transition Arrows: Coin Change

◆ Coin Change — Transition Visualization

coins=[1,2,5], amount=7

dp[i] = min coins to make amount i

(∞ = amount+1 = 'impossible')

i: 0 1 2 3 4 5 6 7
dp: [0] [1] [1] [2] [2] [1] [2] [2]
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑

© DP Mastery Guide — Java Edition Page 31

Dynamic Programming Mastery Guide — Java A Complete Reference

base +1 +1 +1 +2 +5 +5+1 +5+2

←2→ ←2→ ←2→ ←5→

Answer: dp[7] = 2 (coins: 5 + 2)

Transitions for dp[7]:

Use coin 1: dp[6] + 1 = 2 + 1 = 3
Use coin 2: dp[5] + 1 = 1 + 1 = 2 ← MINIMUM
Use coin 5: dp[2] + 1 = 1 + 1 = 2 ← ALSO MINIMUM

© DP Mastery Guide — Java Edition Page 32

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

8
Comparison Tables

8.1 Problem Complexity Summary

Problem Approach Time Space (Optimized)

Fibonacci 1D DP O(n) O(1)

Climbing Stairs 1D DP O(n) O(1)

0/1 Knapsack 2D DP O(n·W) O(W)

LCS 2D DP O(m·n) O(min(m,n))

1D DP / Binary
LIS O(n log n) O(n)
Search

Coin Change 1D DP O(amount·coins) O(amount)

Edit Distance 2D DP O(m·n) O(n)

Matrix Chain Interval DP O(n³) O(n²)

Palindrome Partition 2-phase DP O(n²) O(n²)

8.2 Recursion vs Memoization vs Tabulation

Feature Recursion Memoization Tabulation

Subproblem reuse ■ None ■ Yes (cache) ■ Yes (table)

Stack usage O(n) O(n) O(1)

Code complexity Simple Simple++ Medium

Space efficiency Worst Medium Best (optimizable)

Stack overflow risk High High None

Unused subproblems Computed Skipped ■ Computed

© DP Mastery Guide — Java Edition Page 33

Dynamic Programming Mastery Guide — Java A Complete Reference

Feature Recursion Memoization Tabulation

Cache locality Poor Poor Excellent ■

Interview preference Show first Explain Final answer

8.3 DP Type Selection Guide

Scenario DP Type Dimension

Single array/string, no constraint Linear 1D O(n)

Two strings/sequences 2D Grid O(m×n)

Array with capacity/budget Knapsack O(n×W)

2D matrix movement Grid DP O(rows×cols)

Range/interval query Interval DP O(n²)

Tree structure Tree DP (DFS) O(n)

Subset selection (n ≤ 20) Bitmask DP O(2■×n)

Counting digit patterns Digit DP O(digits×states)

© DP Mastery Guide — Java Edition Page 34

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

9
Common Mistakes & Debugging Tips

■ Wrong State Definition

The most common source of bugs. The state must encode ALL information needed.

◆ Common Mistake

// Example: For LCS: dp[i] alone is wrong. You need dp[i][j] for both string position
s.

■ Incorrect Base Cases

Missing or wrong base cases propagate errors to all larger states.

◆ Common Mistake

// Example: For Knapsack: forgetting dp[0][w]=0 for all w causes wrong results.

■ Wrong Iteration Order

In bottom-up, you must fill states in the order their dependencies come first.

◆ Common Mistake

// Example: For 0/1 Knapsack 1D: must go right-to-left, not left-to-right.

■ Off-By-One Errors
Confusing 0-indexed vs 1-indexed DP arrays is very common.

◆ Common Mistake

// Example: dp[i] represents first i items (1-indexed). Access array with items[i-1].

■ Integer Overflow
Adding large DP values can overflow int. Use Long or check bounds.

◆ Common Mistake

// Example: int cost = dp[i][k] + dp[k+1][j] + ... — use long if values are large.

© DP Mastery Guide — Java Edition Page 35

Dynamic Programming Mastery Guide — Java A Complete Reference

■ Not Initializing to Infinity

For minimization problems, initialize dp to Integer.MAX_VALUE or a large sentinel.

◆ Common Mistake

// Example: dp[i] = amount+1 (for coin change) acts as infinity.

■ Forgetting to Return -1 for Impossible Cases

After DP, check if the computed value indicates impossibility.

◆ Common Mistake

// Example: if (dp[amount] > amount) return -1; // impossible in Coin Change

9.1 Debugging Strategy

• Start small: Test with n=1, n=2, n=3 manually and verify DP table values
• Print the DP table: Add a printDP() method to visualize the filled table
• Trace back: After computing dp[n], trace back to see which items were selected
• Check boundary conditions: i=0, j=0, last row/column
• Verify recurrence on paper: Manually compute dp[2][3] using your formula

9.2 Performance Tips

• Always implement brute force first, verify correctness, then optimize
• Use int vs long carefully — know your value ranges
• For large inputs, check if your O(n²) solution will TLE (n > 10■ usually means O(n²) is too slow)
• Consider space optimization only after correctness is confirmed

© DP Mastery Guide — Java Edition Page 36

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

10
Practice Problems

■ Easy Problems
Problem Key Pattern Hint

Min Cost Climbing Stairs 1D DP dp[i] = cost[i] + min(dp[i-1], dp[i-2])

House Robber 1D DP dp[i] = max(dp[i-1], dp[i-2]+nums[i])

Pascal's Triangle 2D DP dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

Best Time to Buy/Sell Stock 1D DP Track minPrice and maxProfit as you scan

Counting Bits 1D DP dp[i] = dp[i>>1] + (i & 1)

Unique Paths (Grid) Grid DP dp[i][j] = dp[i-1][j] + dp[i][j-1]

Nth Tribonacci Number 1D DP dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

■ Medium Problems
Problem Key Pattern Hint

Longest Palindromic
2D DP LCS(s, reverse(s))
Subsequence

Decode Ways 1D DP Check single and double digit decoding

Word Break 1D DP + HashSet dp[i] = OR of dp[j] where s[j..i] in dict

Target Sum 2D DP / DFS+Memo Add/subtract: knapsack variant

Partition Equal Subset Sum Knapsack DP Can we find subset with sum = total/2?

Minimum Path Sum Grid DP dp[i][j] = grid[i][j] + min(up, left)

Maximal Square Grid DP dp[i][j] = min(left, up, diag) + 1

Interleaving String 2D DP dp[i][j] = interleave s1[0..i] and s2[0..j]

© DP Mastery Guide — Java Edition Page 37

Dynamic Programming Mastery Guide — Java A Complete Reference

Problem Key Pattern Hint

Jump Game II Greedy/DP dp[i] = min jumps to reach i

Coin Change 2 (Count Ways) Knapsack DP dp[i] += dp[i-coin] for each coin

■ Hard Problems
Problem Key Pattern Hint

Regular Expression Matching 2D DP Handle '*' matching 0 or more chars

Burst Balloons Interval DP dp[i][j] = max coins from i to j

Scramble String 3D DP/Memo dp[s1][s2] = can s1 be scrambled to s2?

Longest Valid Parentheses 1D DP / Stack dp[i] = length if s[i]=')'

Distinct Subsequences 2D DP dp[i][j] = ways to match t[0..j] in s[0..i]

Stone Game (series) Interval DP Minimax with optimal play

K Inverse Pairs Array 2D DP dp[i][k] = arrays of length i with k inv pairs

Strange Printer Interval DP dp[i][j] = min turns to print s[i..j]

© DP Mastery Guide — Java Edition Page 38

Dynamic Programming Mastery Guide — Java A Complete Reference

CHAPTER

11
Bonus: Space Optimization, Patterns &
Interview Tips

11.1 Space Optimization Techniques

Rolling Array (2 variables)
◆ Rolling Array Optimization

// When dp[i] depends only on dp[i-1] and dp[i-2]

// Instead of: int[] dp = new int[n+1]
// Use: int prev2=dp[0], prev1=dp[1]

int prev2 = 0, prev1 = 1;

for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2; // Your recurrence
prev2 = prev1;
prev1 = curr;
}
// Space: O(1) instead of O(n)

1D Array for Knapsack (Reverse Traversal)

◆ 1D Knapsack — Reverse Traversal

// 2D -> 1D optimization for 0/1 knapsack

// Key: traverse BACKWARDS to prevent item reuse

int[] dp = new int[W + 1];

for (int item : items) {
for (int w = W; w >= [Link]; w--) { // ← BACKWARDS!
dp[w] = [Link](dp[w], dp[w - [Link]] + [Link]);
}
}
// For UNBOUNDED knapsack (item reuse allowed): traverse FORWARDS

© DP Mastery Guide — Java Edition Page 39

Dynamic Programming Mastery Guide — Java A Complete Reference

11.2 Pattern Recognition Shortcuts

If you see... Think...

'Minimum/Maximum of ...' DP optimization (min/max recurrence)

'Count number of ways to ...' DP counting (sum recurrence)

'Is it possible to ...' DP boolean (OR recurrence)

Two strings/arrays compared 2D DP, likely LCS variant

One array, pick some elements 1D DP or Knapsack

Circular array or string Break circle, solve twice

'At most K' constraint Add K as DP dimension

Tree + optimization DFS with DP on subtrees

n ≤ 20, all subsets Bitmask DP

Range [L, R] counting Digit DP

11.3 Interview Tips for DP Questions

1. Always start by identifying if it's a DP problem using the decision flowchart

2. Think out loud — interviewers want to see your thought process, not just code

3. Start with the brute-force recursive solution — explain it, then add memoization

4. Clearly define your state with a verbal statement: 'dp[i] represents ...'

5. Write the recurrence on the whiteboard/paper before coding

6. Handle base cases explicitly and mention why they're correct

7. Analyze complexity before coding — mention both time and space

8. If asked to optimize, first make it correct, then optimize space

9. Practice explaining DP solutions verbally — saying 'I cache subproblems' is key

10. Know the 9 classic problems cold — they appear in 80% of DP interviews

11.4 Quick Complexity Cheat Sheet

© DP Mastery Guide — Java Edition Page 40

Dynamic Programming Mastery Guide — Java A Complete Reference

Pattern Typical Time Typical Space

1D DP O(n) O(1) after optimization

2D DP (strings) O(m·n) O(min(m,n))

Knapsack O(n·W) O(W)

Interval DP O(n³) O(n²)

Bitmask DP O(2■·n) O(2■·n)

Digit DP O(digits·states) O(same)

Tree DP O(n) O(n)

■ Final Advice: Dynamic Programming is a skill that improves dramatically with practice. Solve at
least 2-3 problems from each category in this guide. Focus on understanding the why behind each
state definition and recurrence — not just memorizing solutions. With consistent practice, DP
problems will shift from daunting to enjoyable challenges.

Good Luck! ■

© DP Mastery Guide — Java Edition Page 41