Dynamic programming, or DP, solves a problem by reusing answers to smaller subproblems. It is especially useful when a recursive solution asks the same questions repeatedly. Instead of recalculating an answer, store it and use it when the same state appears again.
Two common approaches are memoization, which adds a cache to top-down recursion, and tabulation, which fills answers from the smallest states upward. Both begin with the same essential work: define what a state means, identify its base cases, and explain how it depends on other states.
Recognizing repeated subproblems
Suppose a person climbs a staircase using moves of one or two steps. Let ways(n) mean the number of ordered move sequences that reach exactly n steps. The last move comes from step n-1 or n-2, giving ways(n) = ways(n-1) + ways(n-2).
A direct recursive calculation of ways(5) asks for ways(4) and ways(3). Calculating ways(4) asks for ways(3) again. Larger inputs repeatedly revisit the same smaller states, causing an exponential amount of work.
The base answer ways(0) is one: there is one empty sequence that climbs no steps. The answer ways(1) is also one. These definitions make the recurrence work at the boundary and are not arbitrary numbers chosen to make an example print correctly.
DP is not a label for every loop or recursive method. Independent subproblems that never repeat may not benefit from caching. Look for overlapping states, and ensure the larger answer can be built correctly from their answers.
Cache keys and sentinel values
A cache key must include every input that can change the answer. In a coin selection problem, an index may matter if only the remaining suffix of coins is available. Caching only by target sum would then mix states with different choices.
The staircase example uses zero as an uncomputed marker because every valid nonnegative staircase has at least one way. In a problem where zero is a legitimate answer, use a separate boolean computed array, a nullable wrapper, or a sentinel that cannot be a result.
Keep a memo local to one input problem unless the cache key captures all relevant configuration. Reusing answers from one coin set for a different coin set can produce plausible but incorrect results.
The displayed method assumes a nonnegative step count and a correctly sized memo. A public-facing wrapper should validate those inputs. Very large counts also overflow long; memoization reduces repeated work but does not expand the numeric range.
Space optimization and reconstruction
The staircase recurrence only needs the previous two answers. Two rolling variables can therefore reduce auxiliary storage to O(1). Update them carefully using a temporary sum; overwriting an earlier value before calculating the next answer changes the recurrence.
That optimization is less convenient when you also need to reconstruct a chosen solution or inspect every intermediate result. For minimum-cost problems, a predecessor or selected-choice array can record which transition produced the best answer.
DP tables are explanations as well as storage. During development, print a small table and verify it by hand. Only compress the representation after the state and transition are correct. A smaller implementation is not an improvement if it conceals a wrong boundary condition.
Testing the recurrence and its limits
For amount A and C denominations, the coin table takes O(A×C) time and O(A) space. This depends on the numeric amount, not just the number of digits used to write it. An enormous target can require too much memory even with very few coin denominations.
Test zero, a reachable amount, an unreachable amount and a case where a tempting greedy strategy fails. For bounded coins, add available quantities to the model rather than silently reusing the unbounded transition.
The compact coin example assumes a modest amount that safely allows amount+1 and an array of that size. Applications accepting external input should impose resource limits. Counting solutions may also require BigInteger when the number of answers outgrows primitive types.
A useful debugging question is: what does this table entry mean in one sentence? If the answer changes between the loop, return statement and tests, the algorithm's state definition needs correction before further optimization.
Dynamic Programming Summary
- Define a state and its boundaries before writing loops.
- Reuse answers only when every relevant input matches.
- Compute dependencies before their consumers.
- Distinguish counting, minimizing and enumerating solutions.
- Apply these ideas in coding challenges.
Dynamic Programming Examples
Each example shows the code, the output it produces and what each part does.
Top-down memoization in Java
Save this program as StairMemoExample.java. A zero cache entry means an uncomputed positive-step state.
The eight sequences differ by move order: for example, 1,2,2 and 2,1,2 are separate ways. If you instead wanted unordered combinations, you would need a different state or transition; this recurrence would count too much.
public class StairMemoExample {
static long ways(int steps, long[] memo) {
if (steps <= 1) return 1;
if (memo[steps] != 0) return memo[steps];
memo[steps] = ways(steps - 1, memo) + ways(steps - 2, memo);
return memo[steps];
}
public static void main(String[] args) {
int steps = 5;
System.out.println(ways(steps, new long[steps + 1]));
}
}8Line-by-line explanation
- Lines 2 to 3The two base states return one directly.
- Line 4A previously stored answer is returned without more recursive calls.
- Lines 5 to 6The first computation stores the sum so later calls can reuse it.
- Lines 10 to 11The array covers indices zero through five and is shared throughout this calculation.
Bottom-up tabulation
This version makes dependencies visible in a loop instead of recursive calls.
Both staircase versions compute O(n) states with constant work per state. Memoization uses O(n) array space and up to O(n) call-stack space. Tabulation uses O(n) array space without recursive stack growth.
public class StairTableExample {
static long ways(int steps) {
if (steps < 0) {
throw new IllegalArgumentException("Steps cannot be negative");
}
long[] table = new long[steps + 1];
table[0] = 1;
for (int current = 1; current <= steps; current++) {
table[current] = table[current - 1];
if (current >= 2) table[current] += table[current - 2];
}
return table[steps];
}
public static void main(String[] args) {
System.out.println(ways(0));
System.out.println(ways(5));
}
}1
8Line-by-line explanation
- Lines 3 to 5Invalid negative input is rejected before allocating the table.
- Line 7The empty-route base case initializes the first state.
- Lines 8 to 10Increasing indices ensure both predecessor answers already exist.
- Lines 16 to 17The program checks the zero boundary and a nontrivial staircase.
Minimum coins for an exact amount
Here each positive coin denomination can be used repeatedly. We minimize the number of coins, rather than count combinations.
The greedy choice of the largest coin gives 4+1+1 for six, using three coins. The DP comparison finds 3+3 and improves that answer. Greedy rules must be proved for their problem; they are not interchangeable with DP.
import java.util.Arrays;
public class MinimumCoinExample {
static int minimumCoins(int[] coins, int amount) {
if (amount < 0) throw new IllegalArgumentException("Negative amount");
for (int coin : coins) {
if (coin <= 0) throw new IllegalArgumentException("Positive coins required");
}
int unreachable = amount + 1;
int[] best = new int[amount + 1];
Arrays.fill(best, unreachable);
best[0] = 0;
for (int sum = 1; sum <= amount; sum++) {
for (int coin : coins) {
if (coin <= sum && best[sum - coin] != unreachable) {
best[sum] = Math.min(best[sum], best[sum - coin] + 1);
}
}
}
return best[amount] == unreachable ? -1 : best[amount];
}
public static void main(String[] args) {
System.out.println(minimumCoins(new int[]{1, 3, 4}, 6));
System.out.println(minimumCoins(new int[]{4, 6}, 5));
}
}2
-1Line-by-line explanation
- Lines 5 to 8Negative targets and nonpositive denominations are rejected.
- Lines 9 to 12Unreachable states start above any feasible coin count; amount zero needs no coins.
- Lines 13 to 17Each denomination proposes one coin plus a previously reachable smaller amount.
- Line 20An unchanged unreachable marker becomes the public result minus one.
- Lines 24 to 25Six is made with two threes; five cannot be made from fours and sixes.
Dynamic Programming FAQ
Is tabulation always faster than memoization?
No. Memoization can avoid states never requested, while tabulation avoids recursion overhead. Compare the actual state space and access pattern.
Can DP find an actual solution rather than just its cost?
Yes. Record the choice or predecessor for improved entries, then follow those records backward to reconstruct a solution.
How do I recognise a dynamic programming problem?
Look for two signs: the same smaller subproblems are solved again and again, and the best answer can be built from best answers to those subproblems. Counting ways, finding a minimum or maximum cost, and questions about prefixes of strings or arrays often fit.
What is the difference between dynamic programming and divide and conquer?
Both split a problem into smaller ones. In divide and conquer, such as merge sort, the subproblems don't overlap, so each is solved once anyway. Dynamic programming is for overlapping subproblems, where storing and reusing answers removes the repeated work.
Which dynamic programming problems should I practise first?
Climbing stairs and Fibonacci-style counting, minimum coin change, the 0/1 knapsack problem, longest common subsequence and edit distance. Together they cover one-dimensional tables, two-dimensional tables and reconstructing an actual solution.
Dynamic Programming Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What does ways(0) = 1 mean in the staircase problem?
Using unlimited coins 1, 3 and 4, what is the minimum count for amount 6?
Dynamic Programming Quiz
2 questions to check what you learned.
How does memoization avoid repeated work?
- It stores an answer under its state and reuses it
- It removes the base cases
- It converts every recursive problem into sorting
A subproblem depends on both item index and remaining amount. What belongs in its cache key?
- Both index and remaining amount
- Remaining amount only
- The total number of recursive calls so far