Dynamic programming basics: recognising overlapping subproblems and optimal substructure, memoisation versus tabulation, and a worked minimum-coins example with space optimisation.
Dynamic programming (DP) solves a problem by combining answers to smaller subproblems, storing each answer so it is computed once. It applies when:
fib(3) repeatedly).Two styles: memoisation (recursion plus a cache, top-down) and tabulation (fill a table in order, bottom-up, no recursion). Minimum coins: dp[a] = 1 + min(dp[a - c]) over coins c, O(amount × coins) time.
Many problems have a recursive definition that, written naively, recomputes the same thing exponentially many times. DP removes the repetition by remembering.
naive fib(5)
fib(5)
/ \
fib(4) fib(3) <- fib(3) computed twice
/ \ / \
fib(3) fib(2) fib(2) fib(1) <- fib(2) three times
Naive: O(1.618ⁿ). With a cache: each fib(k) computed once, O(n).
| Memoisation (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| Shape | recursive function + Dictionary/array cache |
loop filling an array in dependency order |
| Computes | only states actually reached | usually every state |
| Stack risk | yes, depth can overflow | none |
| Space optimisation | hard | easy (keep only the last row) |
| Easier to write | often, follows the recurrence | needs the right iteration order |
dp[a] = fewest coins to make amount a.dp[a] = 1 + min(dp[a - c]) for each coin c ≤ a.dp[0] = 0.dp[amount], or "impossible" if still infinite.Complexity: O(amount × coins) time, O(amount) space.
A promotions engine chose which vouchers to apply to a basket by trying every subset: O(2ⁿ). With 25 eligible vouchers it took seconds and timed out at checkout. The constraint was a cap on total discount per basket, so it was a 0/1 knapsack. A DP over (voucher index, discount in cents up to the cap) made it O(n × cap), a few milliseconds, with the same results as brute force in a property-based test.
Checks whether the candidate can recognise when DP applies and build a correct solution.
Green flags
Red flags
Ask three questions:
If yes to all three, DP turns exponential into polynomial: time = number of states × work per state.
Coins {1, 3, 4}, amount 6.
a : 0 1 2 3 4 5 6
dp[a] : 0 1 2 1 1 2 2
^ dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + min(2, 1, 2) = 2 (3 + 3)
Greedy (largest coin first) gives 4 + 1 + 1 = 3 coins, which is wrong. DP considers every last coin and keeps the best.
Store which coin achieved the minimum, then walk back:
var choice = new int[amount + 1];
// inside the loop when you improve dp[a]: choice[a] = c;
var used = new List<int>();
for (int a = amount; a > 0; a -= choice[a]) used.Add(choice[a]);
Interviewers often follow up with "which coins?", and production code almost always needs the plan, not just the number.
dp[i, j] = edits to turn the first i chars of s into the first j chars of t.
"" k i t t e n
"" 0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3 <- distance("sitting", "kitten") = 3
dp[i,j] = s[i-1]==t[j-1] ? dp[i-1,j-1]
: 1 + min(dp[i-1,j] (delete),
dp[i,j-1] (insert),
dp[i-1,j-1]) (replace)
O(n · m) time. Each row only needs the previous row, so space drops from O(n · m) to O(m).
(int i, int j), or better, a 2D array when the ranges are known (much faster than a dictionary).Dictionary memo shared across requests is not thread-safe and grows forever. Keep the memo local to one computation.| Pattern | Example | State |
|---|---|---|
| 1D linear | climbing stairs, house robber, min coins | dp[i] |
| Two strings | LCS, edit distance, diff | dp[i, j] |
| Knapsack | budget, vouchers, capacity | dp[item, capacity] |
| Intervals | weighted scheduling, matrix chain | dp[i] with binary search for previous compatible |
| Grid paths | unique paths, min path sum | dp[r, c] |
// Compare naive vs memoised vs tabulated Fibonacci
using System.Diagnostics;
static long Naive(int n) => n < 2 ? n : Naive(n - 1) + Naive(n - 2);
static long Memo(int n, long[] memo)
{
if (n < 2) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = Memo(n - 1, memo) + Memo(n - 2, memo);
}
static long Table(int n)
{
long prev = 0, cur = 1;
for (int i = 2; i <= n; i++) (prev, cur) = (cur, prev + cur);
return n == 0 ? 0 : cur;
}
var sw = Stopwatch.StartNew();
Console.WriteLine($"{Naive(40)} naive {sw.ElapsedMilliseconds} ms");
sw.Restart();
Console.WriteLine($"{Memo(40, new long[41])} memo {sw.Elapsed.TotalMilliseconds:F3} ms");
sw.Restart();
Console.WriteLine($"{Table(90)} table(90) {sw.Elapsed.TotalMilliseconds:F3} ms");
Naive(40) makes about 330 million calls; the others make 40.
// Minimum coins: tabulation, O(amount * coins) time, O(amount) space
public static (int Count, List<int> Coins)? MinCoins(int[] coins, int amount)
{
const int Inf = int.MaxValue;
var dp = new int[amount + 1];
var choice = new int[amount + 1];
Array.Fill(dp, Inf);
dp[0] = 0;
for (int a = 1; a <= amount; a++)
foreach (var c in coins)
if (c <= a && dp[a - c] != Inf && dp[a - c] + 1 < dp[a])
{
dp[a] = dp[a - c] + 1;
choice[a] = c;
}
if (dp[amount] == Inf) return null;
var used = new List<int>();
for (int a = amount; a > 0; a -= choice[a]) used.Add(choice[a]);
return (dp[amount], used);
}
// Memoised (top-down) version of the same recurrence
public static int MinCoinsMemo(int[] coins, int amount)
{
var memo = new int?[amount + 1];
int Solve(int a)
{
if (a == 0) return 0;
if (memo[a] is int cached) return cached;
int best = int.MaxValue;
foreach (var c in coins)
if (c <= a && Solve(a - c) is var sub && sub != int.MaxValue)
best = Math.Min(best, sub + 1);
return (memo[a] = best).Value;
}
return Solve(amount); // recursion depth up to amount: prefer tabulation for big amounts
}
// Edit distance with O(m) space (two rows)
public static int Levenshtein(ReadOnlySpan<char> s, ReadOnlySpan<char> t)
{
var prev = new int[t.Length + 1];
var cur = new int[t.Length + 1];
for (int j = 0; j <= t.Length; j++) prev[j] = j;
for (int i = 1; i <= s.Length; i++)
{
cur[0] = i;
for (int j = 1; j <= t.Length; j++)
cur[j] = s[i - 1] == t[j - 1]
? prev[j - 1]
: 1 + Math.Min(Math.Min(prev[j], cur[j - 1]), prev[j - 1]);
(prev, cur) = (cur, prev);
}
return prev[t.Length];
}
Mistake: Using greedy where DP is needed, for example coins {1, 3, 4} for amount 6. Why it is wrong: Taking the largest coin first gives 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is optimal. Greedy commits early and never reconsiders. Instead: Use DP unless you can prove the greedy choice is always safe (an exchange argument).
Mistake: Defining the state vaguely.
Why it is wrong: If dp[i] has no precise meaning, the recurrence and base cases come out wrong.
Instead: Write the definition in one sentence first, such as "dp[a] is the fewest coins that sum to exactly a".
Mistake: Memoising with deep recursion on large inputs. Why it is wrong: Recursion depth can equal the input size, and a stack overflow in .NET cannot be caught; it ends the process. C# does not guarantee tail-call optimisation to save you. Instead: Use bottom-up tabulation for large state spaces, or keep memoisation only when depth is known to be small.
Mistake: Caching in a Dictionary<string, int> with string-concatenated keys.
Why it is wrong: Each lookup allocates and hashes a string, which is far slower than array indexing.
Instead: Use arrays for dense integer states, or value-tuple keys such as (int I, int J) when states are sparse.
Mistake: Sharing a static memo across requests.
Why it is wrong: A plain Dictionary<TKey,TValue> is not thread-safe, and the cache grows without limit.
Instead: Keep the memo local to one computation.
Mistake: Returning only the optimal value. Why it is wrong: Real features need the plan: which vouchers, which edits, which bookings. Instead: Store the choice per state and reconstruct by walking back from the answer.
Mistake: Keeping the full table when only the previous row is needed. Why it is wrong: O(n · m) memory can reach gigabytes for long strings. Instead: Keep two rows (O(m) space) when you do not need full reconstruction.
A senior engineer recognises DP in disguise. The interview problem is minimum coins; the production problem is "checkout times out once 25 vouchers are eligible". The skill is mapping the business rule to a state and a recurrence, then estimating the state count (for example n × discount cap) to check it is feasible before writing code.
| Question | Memoisation (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Easier to write from the recurrence | Yes | Needs the right iteration order |
| Computes only reachable states | Yes, good for sparse state spaces | Usually fills every state |
| Stack overflow risk | Yes, depth can match input size | None |
| Space optimisation (rolling rows) | Hard | Easy |
| Typical production choice | Small, sparse or irregular state spaces | Large, dense state spaces on hot paths |
Seniors also validate DP against brute force on small inputs with property-based tests (FsCheck or CsCheck), because DP bugs are usually off-by-one errors in base cases or iteration order and produce plausible but wrong answers. And they know when not to bother: if n is tiny and fixed, brute force is simpler and obviously correct; if the state space is too big, they use heuristics or approximations and document the trade-off.
A greedy algorithm builds a solution step by step, always taking the locally best choice and never revisiting it. It is fast and simple, but only optimal when the problem has the greedy-choice property (a locally best choice is part of some optimal solution) and optimal substructure.
In production, greedy is often a good-enough heuristic (bin packing, load balancing) as long as you know it is approximate.
Recursion is a function solving a problem by calling itself on a smaller version of it. Every recursive function needs:
Each call pushes a frame on the thread's call stack (about 1 MB by default on Windows). Too deep and you get a StackOverflowException, which cannot be caught and kills the process. Recursion fits naturally recursive data (trees, nested JSON, folders), but use a loop with an explicit Stack<T> or Queue<T> when depth can be large or is controlled by input.
Space complexity is how the extra memory an algorithm needs grows with input size. Usually we quote auxiliary space, not counting the input.
HashSet of seen items: O(n).In .NET, space also means allocations and GC pressure: an O(n) algorithm that allocates per item can be slower than one that reuses a buffer. Common trade: spend O(n) memory (a dictionary, memo table) to save time.
How to tell it (STAR)
In my role at [company], our checkout started timing out after a marketing campaign. I profiled it and found the voucher engine tried every subset, which is 2 to the power n, and n had grown to [25]. I recognised it as a knapsack problem with the discount cap as capacity, rewrote it as a bottom-up DP and kept brute force as a test oracle. Latency went from [8 seconds] back to [under 5 ms] for that step, and the campaign stayed live.
Last updated 23 Oct 2026.