Chapter 22
Dynamic Programming (Basics) in
Java
Java Data Structures & Algorithms Series
Dynamic Programming (DP) is an optimization technique that solves complex problems by
breaking them into overlapping subproblems, solving each subproblem only once, and storing the
result to avoid recomputation. The secret is: every DP solution starts as recursion.
1 The 4-Step DP Pipeline
Always follow this exact progression for every DP problem:
Step 1: Recursion (brute force — understand the problem)
↓
Step 2: Memoization (top-down DP — cache recursion results)
↓
Step 3: Tabulation (bottom-up DP — fill table iteratively)
↓
Step 4: Space Optimization (reduce space from O(n) to O(1))
We will apply all 4 steps to every problem in this chapter.
2 When Does DP Apply?
A problem is a DP problem if it has:
Overlapping Subproblems — same subproblem is solved multiple times
Optimal Substructure — optimal solution built from optimal subsolutions
Count(fib(5)):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
fib(3) computed TWICE, fib(2) computed THREE times → overlapping subproblems!
3 Pattern 1 — Fibonacci (The Hello World of DP)
Step 1 — Pure Recursion (Exponential O(2ⁿ))
public static int fibRecursion(int n) {
if (n <= 1) return n; // base cases: fib(0)=0, fib(1)=1
return fibRecursion(n - 1) + fibRecursion(n - 2);
}
// Time: O(2^n) — extremely slow for n=50
Step 2 — Memoization (Top-Down) O(n)
public static int fibMemo(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // already computed, return cached
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Driver: fibMemo(n, new int[n+1] filled with -1)
// Time: O(n) | Space: O(n) — memo array + recursion stack
Step 3 — Tabulation (Bottom-Up) O(n)
public static 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];
}
// Time: O(n) | Space: O(n)
Step 4 — Space Optimized O(1) Space
public static int fibOptimal(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;
}
// Time: O(n) | Space: O(1) ← only 2 variables needed!
4 Pattern 2 — Climbing Stairs
Problem: You can climb 1 or 2 steps at a time. How many ways to reach step n?
n=4:
[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2] → 5 ways
💡 This is exactly Fibonacci! ways(n) = ways(n-1) + ways(n-2)
// Step 1: Recursion
public static int climbRecursion(int n) {
if (n <= 1) return 1; // base: 0 steps=1 way, 1 step=1 way
return climbRecursion(n-1) + climbRecursion(n-2);
}
// Step 2: Memoization
public static int climbMemo(int n, int[] memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
return memo[n] = climbMemo(n-1, memo) + climbMemo(n-2, memo);
}
// Step 4: Space Optimized (jump directly to best solution)
public static int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Time: O(n) | Space: O(1)
5 Pattern 3 — House Robber
Problem: Rob houses along a street. Can't rob two adjacent houses. Maximize money.
Houses: [2, 7, 9, 3, 1]
Best: 2 + 9 + 1 = 12 OR 7 + 3 = 10 → Answer: 12
// Step 1: Recursion — at each house, rob it or skip it
public static int robRecursion(int[] nums, int i) {
if (i < 0) return 0;
int rob = nums[i] + robRecursion(nums, i - 2); // rob house i
int noRob = robRecursion(nums, i - 1); // skip house i
return [Link](rob, noRob);
}
// Step 2: Memoization
public static int robMemo(int[] nums, int i, int[] memo) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = [Link](
nums[i] + robMemo(nums, i-2, memo),
robMemo(nums, i-1, memo)
);
}
// Step 3: Tabulation
public static int robTab(int[] nums) {
int n = [Link];
if (n == 1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = [Link](nums[0], nums[1]);
for (int i = 2; i < n; i++)
dp[i] = [Link](nums[i] + dp[i-2], dp[i-1]);
return dp[n-1];
}
// Step 4: Space Optimized
public static int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = [Link](num + prev2, prev1);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Time: O(n) | Space: O(1)
6 Pattern 4 — Coin Change (Minimum Coins)
Problem: Given coins of different denominations, find minimum coins to make amount.
Coins: [1, 5, 6, 9], Amount: 11
Answer: 2 coins → [5, 6] NOT [1,1,9] = 3 coins
// Step 2: Memoization
public static int coinChangeMemo(int[] coins, int amount, int[] memo) {
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo[amount] != Integer.MAX_VALUE) return memo[amount];
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int result = coinChangeMemo(coins, amount - coin, memo);
if (result != -1)
minCoins = [Link](minCoins, result + 1);
}
return memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
}
// Step 3: Tabulation (Most common interview solution)
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1); // fill with "impossible" value
dp[0] = 0; // 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];
}
// Time: O(amount × coins) | Space: O(amount)
Trace for amount=11, coins=[1,5,6,9]:
dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4
dp[5]=1, dp[6]=1, dp[7]=2, dp[8]=2, dp[9]=1
dp[10]=2, dp[11]=2 ✅
7 Pattern 5 — 0/1 Knapsack
Problem: N items with weights and values. Bag capacity W. Maximize value without exceeding
capacity. Each item used at most once.
Items: weight=[2,3,4,5] value=[3,4,5,6] capacity=5
Best: item1(w=2,v=3) + item2(w=3,v=4) = w=5, v=7
// Step 2: Memoization
public static int knapsackMemo(int[] w, int[] v, int n, int cap, int[][] memo) {
if (n == 0 || cap == 0) return 0;
if (memo[n][cap] != -1) return memo[n][cap];
if (w[n-1] > cap)
return memo[n][cap] = knapsackMemo(w, v, n-1, cap, memo);
return memo[n][cap] = [Link](
v[n-1] + knapsackMemo(w, v, n-1, cap - w[n-1], memo), // take item
knapsackMemo(w, v, n-1, cap, memo) // skip item
);
}
// Step 3: Tabulation
public static int knapsack(int[] weight, int[] value, int capacity) {
int n = [Link];
int[][] dp = new int[n + 1][capacity + 1];
// dp[i][c] = max value using first i items with capacity c
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= capacity; c++) {
dp[i][c] = dp[i-1][c]; // Option 1: skip current item
if (weight[i-1] <= c) // Option 2: take current item
dp[i][c] = [Link](dp[i][c],
value[i-1] + dp[i-1][c - weight[i-1]]);
}
}
return dp[n][capacity];
}
// Time: O(n × W) | Space: O(n × W)
Step 4 — Space Optimized (1D dp)
public static int knapsackOptimal(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < [Link]; i++)
// Traverse RIGHT TO LEFT to avoid using same item twice
for (int c = capacity; c >= weight[i]; c--)
dp[c] = [Link](dp[c], value[i] + dp[c - weight[i]]);
return dp[capacity];
}
// Time: O(n × W) | Space: O(W)
8 Pattern 6 — Word Break
Problem: Can string s be segmented into words from dictionary?
s = "leetcode", dict = ["leet", "code"] → true
s = "applepenapple", dict = ["apple", "pen"] → true
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int n = [Link]();
boolean[] dp = new boolean[n + 1];
dp[0] = true; // empty string is always valid
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && [Link]([Link](j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
// Time: O(n²) | Space: O(n)
9 Pattern 7 — Decode Ways
Problem: '1'→A, '2'→B, …, '26'→Z. Count ways to decode a digit string.
"226" → "BZ"(226), "VF"(2,26), "BBF"(2,2,6) → 3 ways
public static int numDecodings(String s) {
int n = [Link]();
if ([Link](0) == '0') return 0; // leading zero = invalid
int[] dp = new int[n + 1];
dp[0] = 1; // empty string = 1 way
dp[1] = 1; // first char (non-zero) = 1 way
for (int i = 2; i <= n; i++) {
int oneDigit = [Link]([Link](i-1, i));
int twoDigit = [Link]([Link](i-2, i));
if (oneDigit >= 1) // valid single digit (1-9)
dp[i] += dp[i-1];
if (twoDigit >= 10 && twoDigit <= 26) // valid two digit (10-26)
dp[i] += dp[i-2];
}
return dp[n];
}
// Time: O(n) | Space: O(n)
10 DP Patterns Cheat Sheet
Pattern Key Decision Example Problems
Linear DP Take/skip current element Fibonacci, Climbing Stairs, House
Robber
Knapsack Include/exclude item 0/1 Knapsack, Subset Sum,
Partition Equal
Unbounded Knapsack Use item multiple times Coin Change, Rod Cutting
String DP Match/skip characters Word Break, Decode Ways
Interval DP Split at every point Matrix Chain, Burst Balloons
2D Grid DP Move right/down Unique Paths, Min Path Sum
11 Full Runnable Java Program
import [Link].*;
public class Chapter22DPBasics {
public static void main(String[] args) {
// Fibonacci
[Link]("Fib(9): " + fibOptimal(9)); // 34
// Climbing Stairs
[Link]("Climb(5): " + climbStairs(5)); // 8
// House Robber
int[] houses = {2, 7, 9, 3, 1};
[Link]("Rob max: " + rob(houses)); // 12
// Coin Change
int[] coins = {1, 5, 6, 9};
[Link]("Min coins(11): " + coinChange(coins, 11)); // 2
// 0/1 Knapsack
int[] weight = {2, 3, 4, 5}, value = {3, 4, 5, 6};
[Link]("Knapsack(5): " +
knapsackOptimal(weight, value, 5)); // 7
// Word Break
[Link]("WordBreak: " +
wordBreak("leetcode", [Link]("leet","code"))); // true
// Decode Ways
[Link]("Decode '226': " + numDecodings("226")); // 3
}
static int fibOptimal(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}
static int climbStairs(int n) {
if (n <= 1) return 1;
int a = 1, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}
static int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int c = [Link](num + prev2, prev1);
prev2 = prev1; prev1 = c;
}
return prev1;
}
static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1); dp[0] = 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];
}
static int knapsackOptimal(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < [Link]; i++)
for (int c = cap; c >= w[i]; c--)
dp[c] = [Link](dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
static boolean wordBreak(String s, List<String> dict) {
Set<String> set = new HashSet<>(dict); int n = [Link]();
boolean[] dp = new boolean[n + 1]; dp[0] = true;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (dp[j] && [Link]([Link](j, i))) { dp[i] = true; break;
}
return dp[n];
}
static int numDecodings(String s) {
int n = [Link](); if ([Link](0) == '0') return 0;
int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++) {
int one = [Link]([Link](i-1, i));
int two = [Link]([Link](i-2, i));
if (one >= 1) dp[i] += dp[i-1];
if (two >= 10 && two <= 26) dp[i] += dp[i-2];
}
return dp[n];
}
}
12 Practice Problems for Chapter 22
Solve in this order:
Difficulty Problem
Easy Fibonacci number (LeetCode #509)
Easy Climbing stairs (LeetCode #70)
Easy Min cost climbing stairs (LeetCode #746)
Medium House robber (LeetCode #198)
Medium House robber II — circular array (LeetCode #213)
Medium Coin change (LeetCode #322)
Medium Word break (LeetCode #139)
Medium Decode ways (LeetCode #91)
Medium 0/1 Knapsack (GFG)
Hard Partition equal subset sum (LeetCode #416)
💡 Key Insight: The single most important DP skill is identifying the recurrence relation —
what decision do you make at each step, and how does the current answer depend on previous
answers?
Once you see that pattern, the rest is mechanical.
Next is Chapter 23 — DP Advanced, where you'll tackle 2D DP problems like LCS, LIS, Edit Distance,
and Matrix Chain — the ones that separate good developers from great ones! 🚀