Definition
- Dynamic programming – an algorithmic technique that solves problems by breaking them into subproblems, solving each subproblem once, and storing the result for reuse.
- Optimal substructure – the property that an optimal solution can be constructed from optimal solutions of its subproblems.
- Overlapping subproblems – the property that a naive recursion visits the same subproblem multiple times.
- Memoization – top-down approach that keeps the natural recursion and caches results on first computation.
- Tabulation – bottom-up approach that fills a table iteratively in dependency order.
- Space optimisation – reducing the table to only the rows or variables the current computation needs.
At the National Bank of India, computing the daily settlement total depends on smaller subtotals that get requested again and again across different reports. Instead of recomputing each subtotal from scratch, the settlement team writes every answer in a ledger the first time it is computed and reads it back for every later request. Dynamic programming is exactly this: solve each piece once, store it, reuse it.
Understanding the Concepts
What is dynamic programming?
Dynamic programming is an algorithmic technique for solving problems that can be broken into smaller subproblems whose results overlap. Instead of solving the same subproblem multiple times, you solve it once, store the result, and reuse it whenever it is needed again. This converts what would be exponential brute-force recursion into polynomial-time computation.
The technique applies to optimisation problems (find the minimum cost, maximum profit, longest sequence) and counting problems (count the number of ways to do something). The key is recognising the two properties that make a problem a DP candidate.
package com.bank.dsa;
// Without DP: exponential time
public class NaiveFibonacci {
public static long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // same subproblems computed many times
}
}
What is optimal substructure?
Optimal substructure means the optimal solution to the whole problem can be constructed from optimal solutions of its subproblems. If you can express the answer to a problem in terms of answers to smaller instances of the same problem, the problem has optimal substructure.
For example, the cheapest way to make change for amount A using coins is one coin plus the cheapest way to make change for the remainder A minus the coin value. The shortest path from city X to city Z through city Y is the shortest path from X to Y plus the shortest path from Y to Z.
package com.bank.dsa;
/**
* Minimum coins to make an amount.
* Optimal substructure: minCoins(amount) = 1 + min(minCoins(amount - coin)) for each coin.
*/
public class OptimalSubstructureDemo {
public static int minCoins(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return Integer.MAX_VALUE;
int best = Integer.MAX_VALUE;
for (int coin : coins) {
int sub = minCoins(coins, amount - coin);
if (sub != Integer.MAX_VALUE) {
best = Math.min(best, 1 + sub);
}
}
return best;
}
public static void main(String[] args) {
int[] denominations = {1, 5, 10};
System.out.println("Min coins for 12: " + minCoins(denominations, 12));
}
}
Min coins for 12: 3
What are overlapping subproblems?
Overlapping subproblems means a naive recursive solution ends up solving the same subproblem multiple times. This is the waste that dynamic programming eliminates by caching.
In the Fibonacci sequence, computing fib(5) calls fib(3) twice and fib(2) three times. In the coin change problem, computing minCoins(12) with coins {1, 5, 10} calls minCoins(7) from both minCoins(12) - 5 and minCoins(8) - 1, and many other amounts are visited repeatedly.
If a problem does not have overlapping subproblems, plain recursion or divide-and-conquer is sufficient. Merge sort, for instance, splits the array into halves that do not overlap, so it does not benefit from DP.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class OverlapCounter {
private static final Map<Integer, Integer> callCounts = new HashMap<>();
public static long fib(int n) {
callCounts.merge(n, 1, Integer::sum);
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
fib(8);
callCounts.entrySet().stream()
.sorted(Map.Entry.comparingByKey())
.forEach(e -> System.out.println("fib(" + e.getKey() + ") called " + e.getValue() + " times"));
}
}
fib(0) called 13 times
fib(1) called 21 times
fib(2) called 13 times
fib(3) called 8 times
fib(4) called 5 times
fib(5) called 3 times
fib(6) called 2 times
fib(7) called 1 times
fib(8) called 1 times
How does memoization work?
Memoization keeps the natural top-down recursion but adds a cache. Before computing a subproblem, check whether the result is already stored. If it is, return it immediately. If not, compute it, store it, and then return it. This ensures each distinct subproblem is solved exactly once.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class MemoizationDemo {
private static final Map<Integer, Integer> memo = new HashMap<>();
public static int minCoins(int[] coins, int amount) {
if (amount == 0) return 0;
if (amount < 0) return Integer.MAX_VALUE;
if (memo.containsKey(amount)) return memo.get(amount);
int best = Integer.MAX_VALUE;
for (int coin : coins) {
int sub = minCoins(coins, amount - coin);
if (sub != Integer.MAX_VALUE) {
best = Math.min(best, 1 + sub);
}
}
memo.put(amount, best);
return best;
}
public static void main(String[] args) {
int[] denominations = {1, 5, 10};
System.out.println("Min coins for 27: " + minCoins(denominations, 27));
}
}
Min coins for 27: 5
How does tabulation work?
Tabulation removes recursion entirely. You define a table (usually an array), fill in the base cases, and iterate in an order where every dependency is already computed before you need it. This avoids recursion-stack overhead and makes space optimisation straightforward.
package com.bank.dsa;
import java.util.Arrays;
public class TabulationDemo {
public static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // sentinel: impossible high value
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) {
dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] denominations = {1, 5, 10};
System.out.println("Min coins for 27: " + minCoins(denominations, 27));
}
}
Min coins for 27: 5
How is memoization different from tabulation?
| Aspect | Memoization (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Direction | Starts at the target, recurses to base cases | Starts at base cases, iterates to target |
| Recursion | Uses the call stack | No recursion at all |
| Subproblem coverage | Solves only reachable states | Solves all states in the table |
| Space optimisation | Hard to drop earlier states from cache | Easy to keep only the last row or few variables |
| Stack overflow risk | Yes, for deep recursion | None |
| Code style | More natural for tree-shaped problems | More natural for grid or sequence problems |
package com.bank.dsa;
/**
* Fibonacci: memoization vs tabulation side by side.
*/
public class MemoVsTabulation {
// Memoization: top-down
private static long[] cache = new long[100];
static { Arrays.fill(cache, -1); }
public static long fibMemo(int n) {
if (n <= 1) return n;
if (cache[n] != -1) return cache[n];
return cache[n] = fibMemo(n - 1) + fibMemo(n - 2);
}
// Tabulation: bottom-up
public static long fibTab(int n) {
if (n <= 1) return n;
long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
long cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
public static void main(String[] args) {
System.out.println("Memo fib(20) = " + fibMemo(20));
System.out.println("Tab fib(20) = " + fibTab(20));
}
}
Memo fib(20) = 6765
Tab fib(20) = 6765
What are the standard DP patterns?
Most interview DP problems fall into a few recurring patterns:
- Fibonacci Numbers : each state depends on a fixed number of previous states (climbing stairs, house robber).
- 0/1 Knapsack : binary include-or-exclude choice under a capacity constraint (subset sum, partition equal subset).
- Unbounded Knapsack : items can repeat, so the capacity sweep goes upward (coin change, rod cutting).
- Longest Common Subsequence : two-sequence grid comparing elements pairwise (edit distance, diff tools).
- Interval DP : choosing a split point within a range (matrix chain multiplication, burst balloons).
- Grid Paths : coordinate-based states moving through a 2D grid (unique paths, minimum path sum).
package com.bank.dsa;
/**
* Pattern recognition example: recognise that this is a Fibonacci-style problem.
* Count distinct ways to reach step n taking 1 or 2 steps at a time.
*/
public class PatternRecognition {
public static long climbStairs(int n) {
if (n <= 1) return 1;
long prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
long cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
public static void main(String[] args) {
System.out.println("Ways to climb 5 stairs: " + climbStairs(5));
}
}
Ways to climb 5 stairs: 8
What are common mistakes when framing a DP problem?
The most common mistake is choosing a state that is too small. If the state does not capture all the information needed to make the next decision, the recurrence will be wrong.
// WRONG: state is only the remaining amount, but we also need to track which items
// we have used if each item can be used at most once.
// This would allow reuse of items, solving unbounded knapsack instead of 0/1.
public static int knapsackWrong(int[] weights, int[] values, int capacity) {
if (capacity <= 0) return 0;
int best = 0;
for (int i = 0; i < weights.length; i++) {
if (weights[i] <= capacity) {
best = Math.max(best, values[i] + knapsackWrong(weights, values, capacity - weights[i]));
}
}
return best;
}
// CORRECT: state includes the item index to track which items are still available.
public static int knapsackCorrect(int[] weights, int[] values, int index, int capacity) {
if (index < 0 || capacity <= 0) return 0;
int exclude = knapsackCorrect(weights, values, index - 1, capacity);
int include = 0;
if (weights[index] <= capacity) {
include = values[index] + knapsackCorrect(weights, values, index - 1, capacity - weights[index]);
}
return Math.max(exclude, include);
}
Another mistake is forgetting the base cases. Every DP needs at least one base case where the answer is known without recursion. Missing a base case leads to infinite recursion or wrong answers.
When should you use DP versus greedy?
Greedy algorithms make locally optimal choices at each step and never reconsider. They work when the local optimum leads to the global optimum, such as in activity selection or Huffman coding. But greedy fails when the locally best choice can lead to a globally worse outcome.
The coin change problem illustrates this. With denominations {1, 5, 10}, greedy works: always pick the largest coin that fits. But with denominations {1, 3, 4} and target 6, greedy picks 4 + 1 + 1 = three coins, while the optimal answer is 3 + 3 = two coins. DP tries all possibilities and guarantees the global optimum.
package com.bank.dsa;
public class GreedyVsDp {
// Greedy: always pick the largest coin that fits
public static int greedyCoins(int[] coins, int amount) {
int count = 0;
for (int i = coins.length - 1; i >= 0 && amount > 0; i--) {
while (coins[i] <= amount) {
amount -= coins[i];
count++;
}
}
return amount == 0 ? count : -1;
}
// DP: guaranteed optimal
public static int dpCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
java.util.Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int coin : coins) {
if (coin <= a) dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
int[] coins = {1, 3, 4};
int amount = 6;
System.out.println("Greedy: " + greedyCoins(coins, amount) + " coins");
System.out.println("DP: " + dpCoins(coins, amount) + " coins");
}
}
Greedy: 3 coins
DP: 2 coins
What should a senior engineer know?
A senior engineer should understand that many two-dimensional DP tables compress to one-dimensional arrays (or two rolling rows) once you notice that each row depends only on the previous row. This reduces space from O(n * m) to O(min(n, m)).
The complexity of knapsack-style problems is pseudo-polynomial: polynomial in the numeric value of the capacity, not in the number of bits needed to represent it. This is why knapsack is NP-hard in general but tractable for small capacities.
State design is the hardest part of DP. The state must capture everything needed to extend the solution, but nothing more. A state with too many dimensions makes the problem intractable; a state with too few dimensions makes the recurrence incorrect.
Visual Overview
How to Identify a DP Problem
────────────────────────────
┌──────────────────────────────────┐
│ Does the problem have │
│ OPTIMAL SUBSTRUCTURE? │
│ (best answer = combo of bests) │
└──────────┬───────────────────────┘
│ Yes
▼
┌──────────────────────────────────┐
│ Does the problem have │
│ OVERLAPPING SUBPROBLEMS? │
│ (same subproblem solved twice+) │
└──────────┬───────────────────────┘
│ Yes
▼
┌──────────────────────────────────┐
│ USE DYNAMIC PROGRAMMING │
│ │
│ Choose approach: │
│ ┌──────────┐ ┌──────────────┐ │
│ │ Memoize │ │ Tabulate │ │
│ │ top-down │ │ bottom-up │ │
│ │ + cache │ │ + fill table │ │
│ └──────────┘ └──────────────┘ │
└──────────────────────────────────┘
Memoization vs Tabulation
─────────────────────────
Top-Down (Memoization) Bottom-Up (Tabulation)
────────────────────── ──────────────────────
solve(n) dp[0] = base
└─ solve(n-1) dp[1] = f(dp[0])
└─ solve(n-2) dp[2] = f(dp[1], dp[0])
└─ ... ...
└─ base case dp[n] = f(dp[n-1], dp[n-2])
Cache stores results Table filled in order
Recursion stack needed No recursion stack
Key Takeaway
Dynamic programming applies when a problem has two specific properties. The first is optimal substructure, meaning the best overall answer can be assembled from the best answers to smaller subproblems. The second is overlapping subproblems, meaning a naive recursion would solve the same subproblem many times. When both properties hold, caching subproblem answers converts exponential brute-force recursion into polynomial-time computation.
There are two implementation styles. Memoization is top-down: you keep the natural recursion but add a cache that stores each result on first computation and returns the stored value on repeat calls. Tabulation is bottom-up: you fill a table starting from the base cases in an order where every dependency is already computed, which avoids recursion-stack overhead and makes space optimisation straightforward. Both give the same asymptotic complexity but differ in practical characteristics.
At the National Bank of India, Rajesh recognised that an interest projection engine was recomputing the same intermediate subtotals repeatedly across reports, which was the classic sign of overlapping subproblems. The projection was built from smaller projections, so it had optimal substructure. He implemented it both top-down with a cache and bottom-up with rolling variables, and the bottom-up version ran in linear time with constant memory.
The standard DP patterns that cover most interview problems are Fibonacci Numbers, 0/1 Knapsack, Unbounded Knapsack, Longest Common Subsequence, Interval DP, and Grid Paths. Recognising which pattern a problem belongs to is half the battle.
Remember one sentence: a problem is a dynamic programming candidate when the same subproblems repeat and the optimal answer is built from optimal sub-answers, and you fix it by solving each subproblem once.
---