Write the brute-force recursion. Notice it solves the same subproblem over and over. Cache it. That is the whole method, and it works every single time.
DP has a reputation for requiring a flash of insight. It does not. It requires a procedure, applied patiently: define the state, write the recurrence, fix the base cases, choose an evaluation order, and read off the answer. The procedure below turns most DP questions into bookkeeping.
n is 1000. That gap is the question.4 + 1 + 1, three coins. DP finds 3 + 3, two coins. If you cannot prove the greedy exchange, use DP.solve(k) appears in several branches, the exponential cost is pure repetition. Store each result the first time and reuse it. The running time collapses from “number of paths through the tree” to “number of distinct states”.Dictionary or an array.StackOverflowException. You cannot catch that one.Dictionary memo, and you have a correct memoised solution in about four extra lines. Then convert to bottom-up and compress the space. Narrating that progression, brute force to memoised to tabulated to space-optimised, is worth more than jumping straight to the final answer.Answer these in order, out loud, before writing code. They are the whole method.
best[v] = fewest coins summing to exactly v.best[v] = 1 + min(best[v - c]) over every coin c ≤ v.best[0] = 0.v, from 1 to amount.best[amount], unless it is still the sentinel.i elements” does not compose, but “the LIS ending at i” does. Redefine the state before you fight the recurrence.public static class TemplateA
{
/// <summary>
/// Template A: the brute-force recursion plus a memo. Each placeholder from the
/// five questions is a delegate, so one method fits many problems.
/// </summary>
/// <param name="n">The whole problem, for example the top step or the full amount.</param>
/// <param name="isBase">True when the answer is known without recursion.</param>
/// <param name="baseValue">That known answer for a base state.</param>
/// <param name="transitions">The smaller states one choice away.</param>
/// <param name="combine">How the answers of those smaller states merge.</param>
/// <returns>The answer for state n.</returns>
/// <example>
/// Climbing Stairs: <c>Solve(5, s => s <= 2, s => s, s => [s - 1, s - 2],
/// xs => xs.Sum())</c> returns 8.
/// </example>
public static long Solve(
int n,
Func<int, bool> isBase,
Func<int, long> baseValue,
Func<int, IEnumerable<int>> transitions,
Func<IEnumerable<long>, long> combine)
{
// C# has no @cache. A Dictionary keyed by state plays that role.
// It lives inside this call, so answers never leak between inputs.
var memo = new Dictionary<int, long>();
// A local function can call itself, which is all the recursion needs.
long Best(int state)
{
// Seen before: return the stored answer, so each state costs work once.
if (memo.TryGetValue(state, out long hit))
{
return hit;
}
// isBase(state): Climbing Stairs: step <= 2. Coin Change: value == 0.
// baseValue(state): Climbing Stairs: step itself. Coin Change: 0 coins.
// transitions(state): Climbing Stairs: step - 1 and step - 2.
// Coin Change: value - coin, for every coin that fits.
// combine: Climbing Stairs: sum (ways add up).
// Coin Change: 1 + min (one more coin on the best smaller answer).
long answer = isBase(state)
? baseValue(state)
: combine(transitions(state).Select(Best));
// Store before returning, so a repeat call is a cache hit.
memo[state] = answer;
return answer;
}
// Ask for the whole problem. Recursion solves the smaller states first.
return Best(n);
}
}
C# has no @cache decorator. You write the memo yourself: a Dictionary<int, long> for sparse states, or a plain array when states are small integers. For a state with two parts, key the dictionary on a tuple such as (int, int). Value tuples hash and compare by value, so they work as keys. The memo is created inside the call, so results never leak between different inputs. The recursive helper is a local function, which C# allows to call itself. In the template each placeholder is a delegate parameter, so the same method really runs. In an interview you would inline them.
Reading the figure. Green boxes are calls that run their body and store a result. Blue dashed boxes are repeat calls that the memo answers at once. The cache row shows the order the answers land. The base cases 2 and 1 are stored first, and ways(5) = 8 is stored last.
public static class TemplateB
{
/// <summary>
/// Template B: fill a 1D table from slot 0 up to slot n. Every placeholder is a
/// parameter, so you can see exactly which part changes from problem to problem.
/// </summary>
/// <param name="n">The size of the whole problem. Coin Change: the amount.</param>
/// <param name="initial">The "nothing found yet" value every slot starts with.</param>
/// <param name="baseValue">The known answer for slot 0, the empty problem.</param>
/// <param name="choices">Every legal LAST move for subproblem i.</param>
/// <param name="cost">What one move adds on top of the smaller answer.</param>
/// <param name="better">Picks between the current table[i] and a new candidate.</param>
/// <returns>table[n], the answer to the whole problem.</returns>
/// <example>
/// Coin Change with coins [1, 3, 4]: <c>SolveTable(6, 7, 0,
/// i => coins.Where(c => c <= i), c => 1, Math.Min)</c> returns 2.
/// </example>
public static int SolveTable(
int n,
int initial,
int baseValue,
Func<int, IEnumerable<int>> choices,
Func<int, int> cost,
Func<int, int, int> better)
{
// table[i] holds the answer for subproblem i. Coin Change: amount i.
// n + 1: +1 so index n exists, slots 0..n.
var table = new int[n + 1];
// initial: the "nothing found yet" value.
// Coin Change: amount + 1, a sentinel no real answer can reach.
// Counting ways: 0, because no ways are found yet.
Array.Fill(table, initial);
// baseValue: the known answer for the empty subproblem in slot 0.
// Coin Change: 0, because zero coins make amount 0.
// Counting ways: 1, because taking nothing is one way to make 0.
table[0] = baseValue;
// i is the subproblem being solved. Start at 1: slot 0 is the base case.
// i <= n so that slot n is included.
// Invariant: table[0..i-1] are all final when the pass for i starts.
for (int i = 1; i <= n; i++)
{
// choices(i): every legal LAST move for subproblem i.
// Coin Change: each coin with coin <= i (the coins that fit).
foreach (int choice in choices(i))
{
// table[i - choice]: the smaller subproblem left after this choice.
// Coin Change: pay one coin, and i - coin is still to be made.
// It is final already, because i - choice < i.
// cost(choice): what this one choice adds on top of that answer.
// Coin Change: 1 (one more coin). Counting ways: 0 (adds nothing).
// better: how to pick between the current table[i] and this candidate.
// Coin Change: Math.Min (keep the fewest coins).
// Counting ways: + (every route to i - choice is a new route to i).
table[i] = better(table[i], table[i - choice] + cost(choice));
}
}
// Slot n holds the answer to the whole problem.
return table[n];
}
}
In plain words: solve every amount from small to large. For each amount, try every possible last move. A last move leaves a smaller amount behind, and that smaller amount is already solved, so you just read table[i - choice]. Add what the move itself costs, then keep the better total. This template shows only the tabulate step. The compress step comes after it works: if slot i only ever reads a fixed few earlier slots, keep just those, like the two variables in Climbing Stairs. For a 2D table where each row reads only the row above, keep two rows with Template C. With the counting choices (better is +, cost is 0), this loop order counts orderings. Swap the loops, as in Coin Change II, to count combinations.
cost(choice) means. Think of each slot as a price tag. table[i - choice] is the price of the smaller problem you land on. cost(choice) is the price of the move itself, the one step that takes you from i - choice up to i. So a candidate total is old price + price of this step.
1, because you count coins. From table[3] = 1, paying one 3-coin gives 1 + 1 = 2 for amount 6.0. Every route to i - choice simply becomes a route to i.cost returns that price.cost never depends on table. It is a fixed fact about the move. better then decides what to do with the candidate: keep the smaller, keep the larger, or add it on.Reading the figure. Each box is one slot table[i]. Grey slot 0 is the base case. Blue slots are final. Amber is the slot being filled. The green arrows on top show the winning move into each slot, labelled with the coin. The bottom row zooms in on i = 6. Each arrow starts at table[6 - coin], which is already final because it sits to the left. Red arrows lose. The green one wins with 2 coins, 3 + 3. Notice that every arrow points right. That is why filling in increasing i is safe.
The same template with every placeholder filled in for Coin Change:
public static class CoinChangeTemplateB
{
/// <summary>Template B with every placeholder filled in for Coin Change.</summary>
/// <param name="coins">Distinct positive denominations, unlimited supply of each.</param>
/// <param name="amount">Target sum, amount >= 0.</param>
/// <returns>The fewest coins summing to exactly amount, or -1 if impossible.</returns>
/// <example>
/// <c>MinCoins([1, 3, 4], 6)</c> returns 2. <c>MinCoins([2], 3)</c> returns -1.
/// </example>
public static int MinCoins(int[] coins, int amount)
{
// initial = amount + 1. A real answer uses at most `amount` coins
// (all 1s), so amount + 1 means "not reachable yet".
int initial = amount + 1;
// amount + 1: +1 so index amount exists, slots 0..amount.
var table = new int[amount + 1];
Array.Fill(table, initial);
// baseValue = 0: zero coins make amount 0.
table[0] = 0;
// i is the amount being solved. Start at 1: slot 0 is the base case.
// i <= amount so that slot amount is included.
// Invariant: table[0..i-1] already hold the fewest coins for those amounts.
for (int i = 1; i <= amount; i++)
{
// choices(i) = the coins that fit, so i - coin never drops below 0.
foreach (int coin in coins)
{
if (coin <= i)
{
// table[i - coin]: fewest coins for what is left after this coin.
// cost(coin) = 1: this coin adds one to the count.
// better = Math.Min: keep the smaller of the old best and this route.
table[i] = Math.Min(table[i], table[i - coin] + 1);
}
}
}
// Still the sentinel means no mix of coins hits amount. -1 signals that.
return table[amount] == initial ? -1 : table[amount];
}
}
public static class TemplateC
{
/// <summary>
/// Template C: when row i depends only on row i - 1, keep two rows, not all of them.
/// </summary>
/// <param name="rows">Number of rows after the base row. LCS: text1.Length.</param>
/// <param name="cols">Number of columns after the base column. LCS: text2.Length.</param>
/// <param name="combine">
/// The recurrence. Gets (i, j, above, left, diagonal) and returns the new cell.
/// </param>
/// <returns>The last cell of the last row.</returns>
/// <example>
/// LCS of "abcde" and "ace": <c>Solve2D(5, 3, (i, j, up, left, diag) =>
/// a[i - 1] == b[j - 1] ? diag + 1 : Math.Max(up, left))</c> returns 3.
/// </example>
public static int Solve2D(int rows, int cols, Func<int, int, int, int, int, int> combine)
{
// previous is row i - 1 of the full table. It starts as row 0, the base row.
// new int[]: every slot starts at 0. LCS: an empty prefix shares 0 letters.
// Edit Distance starts this row as 0, 1, ..., cols instead (j inserts).
// cols + 1: +1 so index cols exists. Slot 0 is the empty prefix.
var previous = new int[cols + 1];
// i is the row being built. Start at 1: row 0 is the base row above.
// i <= rows so that the last row is included.
// Invariant: previous holds the finished row i - 1.
for (int i = 1; i <= rows; i++)
{
// Fresh row. Slot 0 is the base column and keeps its base value, 0.
var current = new int[cols + 1];
// j is the column. Start at 1: column 0 is the base column.
for (int j = 1; j <= cols; j++)
{
// combine: the recurrence, fed the three cells a 2D table would read.
// previous[j] = above, current[j - 1] = left,
// previous[j - 1] = up-left diagonal (- 1 = one column back).
// LCS: diagonal + 1 if the letters match, else max(above, left).
// Edit Distance: diagonal if they match, else 1 + min of all three.
current[j] = combine(i, j, previous[j], current[j - 1], previous[j - 1]);
}
// Row i is done. It becomes the "row above" for row i + 1.
// Arrays are references, so this is a cheap pointer swap, not a copy.
previous = current;
}
// previous is now the last row. Its last slot is the answer.
return previous[cols];
}
}
This drops space from O(rows × cols) to O(cols). Offer it after the 2D version works. It is the standard follow-up on every grid and string DP, and Longest Common Subsequence shows it filled in.
Reading the figure. The top row is previous, the finished row above. The bottom row is current. Amber is current[j], the cell being filled. The three blue arrows are the only cells it reads: previous[j] above, previous[j - 1] on the diagonal, and current[j - 1] on the left. Nothing older is ever read. So the rest of the table can be thrown away.
i”.best[0] = 0 for a minimum, ways[0] = 1 for a count. An empty selection has zero cost but exactly one arrangement.int.MaxValue then adding to it. In C# int.MaxValue + 1 wraps to a large negative number, and Math.Min then picks it. A finite sentinel such as amount + 1 cannot overflow and cannot be reached legitimately.new int[m][] creates m null rows, so table[i][j] throws NullReferenceException. Use a rectangular new int[m, n], or allocate each row in a loop.int overflows silently past about 2.1 billion. Use long, or wrap the add in checked to get an exception instead.You climb a staircase of n steps, taking either 1 or 2 steps at a time. How many distinct ways are there to reach the top?
ways[i] is the number of distinct ways to reach step i.i - 1 or a 2 from step i - 2, and those two sets of routes are disjoint, so ways[i] = ways[i - 1] + ways[i - 2].ways[1] = 1, ways[2] = 2.i.ways[n].That is the Fibonacci sequence, offset by one. Saying so immediately is a good start.
public static class ClimbingStairs
{
/// <summary>Number of distinct ways to climb n steps taking 1 or 2 at a time.</summary>
/// <param name="n">Number of steps, n >= 1.</param>
/// <returns>The count of distinct climbs, as a long.</returns>
/// <example><c>Climb(5)</c> returns 8.</example>
public static long Climb(int n)
{
// Base cases: n = 1 has 1 way, n = 2 has 2 ways (1+1 or 2).
// In both, the answer is n itself.
if (n <= 2)
{
return n;
}
// Only the last two values are ever needed, so keep two variables
// instead of an array. O(1) space.
// long, not int: the count is Fibonacci and passes int.MaxValue at n = 46.
// Seeds: twoBack = ways(1) = 1, oneBack = ways(2) = 2.
long twoBack = 1, oneBack = 2;
// Each pass computes ways(step) for step 3..n. Start at 3: steps 1 and 2
// are the seeds. step <= n so that step n is included.
// Invariant: twoBack = ways(step - 2), oneBack = ways(step - 1).
for (int step = 3; step <= n; step++)
{
// Slide up one step. New count = sum of the two counts below it.
// A tuple assignment swaps both at once, like Python's a, b = b, a + b.
(twoBack, oneBack) = (oneBack, twoBack + oneBack);
}
// After the last pass, oneBack = ways(n).
return oneBack;
}
}
public static class ClimbingStairsSteps
{
/// <summary>Step 1: the brute force, made linear by a memo array.</summary>
/// <param name="n">Number of steps, n >= 1.</param>
/// <returns>The count of distinct climbs.</returns>
/// <example><c>Memo(10)</c> returns 89.</example>
public static long Memo(int n)
{
// memo[step] holds ways(step) once known. 0 means "not computed yet",
// which is safe because every real count is at least 1.
// n + 1: +1 so index n exists.
var memo = new long[n + 1];
long Ways(int step)
{
// Base: step 1 has 1 way, step 2 has 2 ways. Both equal step itself.
if (step <= 2)
{
return step;
}
// 0 = not computed. Anything else is a cache hit.
if (memo[step] != 0)
{
return memo[step];
}
// Last move was a 1 (from step - 1) or a 2 (from step - 2). Add both.
memo[step] = Ways(step - 1) + Ways(step - 2);
return memo[step];
}
return Ways(n);
}
/// <summary>Step 2: the same thing bottom-up, O(n) space.</summary>
/// <param name="n">Number of steps, n >= 1.</param>
/// <returns>The count of distinct climbs.</returns>
/// <example><c>Table(10)</c> returns 89.</example>
public static long Table(int n)
{
// Same base as above: the answer is n for n = 1 or 2.
if (n <= 2)
{
return n;
}
// n + 1: +1 so index n exists. Slot 0 stays 0 and is never read.
var ways = new long[n + 1];
// Base cases: 1 way to reach step 1, 2 ways to reach step 2.
ways[1] = 1;
ways[2] = 2;
// Start at 3: steps 1 and 2 are base cases. i <= n so that n is included.
// Invariant: ways[1..i-1] are all final.
for (int i = 3; i <= n; i++)
{
// i - 1: last move was one step. i - 2: last move was two steps.
ways[i] = ways[i - 1] + ways[i - 2];
}
// Slot n is the top step.
return ways[n];
}
}
Brute force to memoised to tabulated to two variables. Walking an interviewer through that chain in ninety seconds demonstrates the method, which is what the question is for.
Reading the figure. Grey slots are the base cases, 1 way and 2 ways. Each blue slot gets two arrows, one from i - 1 and one from i - 2. Their values add. The green slot is the answer, ways[5] = 8. The bottom row shows the O(1) version. Each pass shifts the pair right by one step, and the right box ends on 8.
Math.Min of the two predecessors plus the cost of the step.0 before the loop reaches them.Math.Max(skip, take + twoBack).n = 1 gives 1, n = 2 gives 2. Both handled by the guard.n = 0: arguably 1, the empty climb. The guard returns 0. Ask which is wanted. It is a fair question.n: the count passes int.MaxValue at n = 46, which is why the code uses long. A long holds up to n = 91. Past that, use System.Numerics.BigInteger.n levels. With about 1 MB of stack, a few thousand levels is fine and a million is not. The loop version has no such limit.Given coin denominations and a target amount, return the fewest coins that sum to exactly that amount, or -1 if it is impossible. You have unlimited coins of each denomination.
[1, 3, 4] and amount 6, greedy takes the largest coin first: 4 + 1 + 1, three coins. The optimum is 3 + 3, two coins. Greedy happens to be correct for real-world currencies, which are designed to make it so, but not in general. Lead with this counterexample. It justifies the whole solution.best[v] is the fewest coins summing to exactly v.c ≤ v, so best[v] = 1 + min(best[v - c]) over all such c.best[0] = 0. Zero coins make zero.v, so best[v - c] is always ready.best[amount], or -1 if it is still the sentinel.public static class CoinChange
{
/// <summary>Fewest coins summing to exactly amount, or -1 if impossible.</summary>
/// <param name="coins">Distinct positive denominations, unlimited supply of each.</param>
/// <param name="amount">Target sum, amount >= 0.</param>
/// <returns>The minimum number of coins, or -1.</returns>
/// <example><c>MinCoins([1, 3, 4], 6)</c> returns 2.</example>
public static int MinCoins(int[] coins, int amount)
{
// Any real answer uses at most `amount` coins (all of value 1), so
// amount + 1 is unreachable and makes a clean finite sentinel.
// int.MaxValue would overflow to a negative number on the + 1 below.
int unreachable = amount + 1;
// amount + 1: +1 so index amount exists, slots 0..amount.
var best = new int[amount + 1];
Array.Fill(best, unreachable);
// Base case: 0 coins make amount 0.
best[0] = 0;
// value is the amount being solved. Start at 1: slot 0 is the base case.
// value <= amount so that amount itself is included.
// Invariant: best[0..value-1] are all final.
for (int value = 1; value <= amount; value++)
{
// Try each coin as the LAST coin used.
foreach (int coin in coins)
{
if (coin <= value) // coin fits, so value - coin >= 0
{
// best[value - coin] coins for the rest, + 1 for this coin.
best[value] = Math.Min(best[value], best[value - coin] + 1);
}
}
}
// -1 is the required "impossible" answer when the sentinel never moved.
return best[amount] == unreachable ? -1 : best[amount];
}
}
coins = [1, 3, 4], amount = 6:
v = 1: best[0]+1 = 1. So best[1] = 1.v = 2: best[1]+1 = 2. So best[2] = 2.v = 3: best[2]+1 = 3, best[0]+1 = 1. So best[3] = 1.v = 4: best[3]+1 = 2, best[1]+1 = 2, best[0]+1 = 1. So best[4] = 1.v = 5: best[4]+1 = 2, best[2]+1 = 3, best[1]+1 = 2. So best[5] = 2.v = 6: best[5]+1 = 3, best[3]+1 = 2, best[2]+1 = 3. So best[6] = 2.The winner at v = 6 comes through the 3-coin, which is exactly the case greedy misses.
Reading the figure. Each circle is an amount still to pay. Each arrow spends one coin and moves left by its value. The red path is greedy, which always takes the biggest coin that fits. The green path is the DP answer. The numbers under the bottom line are best[v] from the table above. Notice that best[3] = 1. That is why the hop from 6 to 3 wins.
public static class CoinChangeWays
{
/// <summary>Coin Change II: how many distinct combinations sum to amount.</summary>
/// <param name="coins">Distinct positive denominations, unlimited supply of each.</param>
/// <param name="amount">Target sum, amount >= 0.</param>
/// <returns>The number of combinations, as a long.</returns>
/// <example><c>Count([1, 2, 5], 5)</c> returns 4.</example>
public static long Count(int[] coins, int amount)
{
// amount + 1: +1 so index amount exists. new long[] starts at 0: no ways yet.
// long, because counts grow fast and int would overflow silently.
var ways = new long[amount + 1];
ways[0] = 1; // one way to make zero: take nothing
// Coins on the OUTSIDE loop. This fixes an order on the coins, so
// 1+3 and 3+1 are counted once. Swapping the loops counts permutations.
// Invariant: after a coin's pass, ways[v] counts the combinations of the
// coins seen so far that sum to v.
foreach (int coin in coins)
{
// Start at coin: smaller values cannot hold this coin.
// value <= amount so amount is included. Forwards, so a coin can repeat.
for (int value = coin; value <= amount; value++)
{
// Each way to make value - coin, plus this coin, makes value.
ways[value] += ways[value - coin];
}
}
return ways[amount];
}
}
amount == 0: returns 0, from the base case.coins = [2] with amount = 3: returns -1.coin <= value guard.-1.int.MaxValue instead of the sentinel breaks: int.MaxValue + 1 overflows to a negative number. The finite sentinel avoids that entirely.Return the length of the longest strictly increasing subsequence of an array. A subsequence may skip elements but must keep the original order.
best[i] is the LIS of the first i elements”, does not compose: knowing that length tells you nothing about whether the next element may be appended, because you do not know what the subsequence ended on. Re-anchor the state: best[i] is the length of the longest increasing subsequence that ends at index i. Now the element is pinned, comparisons are possible, and the recurrence writes itself. This re-anchoring move solves a large family of sequence DPs.best[i] = LIS length ending exactly at i.best[i] = 1 + max(best[j]) over all j < i with nums[j] < nums[i].best[i] = 1. Every element alone is a subsequence of length one.i.best.Max(), not best[^1], because the best subsequence need not end at the last element.public static class Lis
{
/// <summary>Length of the longest strictly increasing subsequence, O(n^2).</summary>
/// <param name="nums">Integers, in any order.</param>
/// <returns>The length of the longest strictly increasing subsequence.</returns>
/// <example><c>Length([10, 9, 2, 5, 3, 7, 101, 18])</c> returns 4.</example>
public static int Length(int[] nums)
{
// Empty input has no subsequence: length 0. Also guards Max() below,
// which throws InvalidOperationException on an empty sequence.
if (nums.Length == 0)
{
return 0;
}
// best[i] is the LIS length ending exactly at index i.
// 1: every element alone is an increasing run of length 1.
var best = new int[nums.Length];
Array.Fill(best, 1);
// i is the end index. Start at 1: index 0 has nothing before it.
// Invariant: best[0..i-1] are all final.
for (int i = 1; i < nums.Length; i++)
{
// j scans every earlier index, 0 up to i - 1.
for (int j = 0; j < i; j++)
{
if (nums[j] < nums[i]) // nums[i] can extend a run ending at j
{
// + 1 for appending nums[i] to that run.
best[i] = Math.Max(best[i], best[j] + 1);
}
}
}
// The optimum can end anywhere, so take the maximum over all endings.
return best.Max();
}
}
public static class LisFast
{
/// <summary>
/// Same answer in O(n log n) by keeping the best tail for each length.
/// tails[k] is the smallest final value of any increasing subsequence of
/// length k + 1 seen so far. It is sorted, so a binary search places each value.
/// </summary>
/// <param name="nums">Integers, in any order.</param>
/// <returns>The length of the longest strictly increasing subsequence.</returns>
/// <example><c>Length([10, 9, 2, 5, 3, 7, 101, 18])</c> returns 4.</example>
public static int Length(int[] nums)
{
// Empty: no lengths reached yet.
var tails = new List<int>();
// Invariant: tails[k] is the smallest tail of any increasing run of
// length k + 1 among the values seen so far, and tails is strictly increasing.
foreach (int value in nums)
{
// BinarySearch returns the index if value is present. Otherwise it
// returns the bitwise complement (~) of the first slot holding a bigger
// value. tails has no duplicates, so a hit is the one equal slot.
int found = tails.BinarySearch(value);
// found >= 0: hit, so value replaces itself (strictly increasing: no extend).
// found < 0: ~found undoes the complement and gives the insertion slot.
int index = found >= 0 ? found : ~found;
if (index == tails.Count) // value beats every tail: slot is past the end
{
tails.Add(value); // extends the longest run found so far
}
else
{
tails[index] = value; // a smaller tail for that length: strictly better
}
}
// One slot per length reached, so the count is the LIS length.
return tails.Count;
}
}
tails array is not itself an increasing subsequence, and its length is the answer. Say that last part unprompted. It is the detail that shows you understand rather than remember.BinarySearch and the ~ trick. List<T>.BinarySearch returns the index when it finds the value. When it does not, it returns a negative number: the bitwise complement of the insertion point. ~found turns it back. With duplicates it may return any matching index, not the first. Here tails is strictly increasing, so there are no duplicates and the result is exact. When duplicates are possible, write the lower-bound loop from Pattern 11 yourself.nums = [10, 9, 2, 5, 3, 7, 101, 18]:
10: append. tails = [10].9: replace index 0. tails = [9].2: replace index 0. tails = [2].5: append. tails = [2, 5].3: replace index 1. tails = [2, 3].7: append. tails = [2, 3, 7].101: append. tails = [2, 3, 7, 101].18: replace index 3. tails = [2, 3, 7, 18].Length 4. Notice [2, 3, 7, 18] happens to be a real subsequence here, but that is a coincidence, not a guarantee.
Reading the figure. Each column is the state after reading the bold value on top. The stack under it is tails, index 0 at the top. Amber marks the one slot that changed, found by BinarySearch. Blue slots stay as they were. A value bigger than every tail appends and makes the stack taller. Any other value replaces a tail with a smaller one. The last column, in green, has height 4.
0. best.Max() throws InvalidOperationException on an empty array, hence the guard.1.1, because the requirement is strictly increasing.< to <= in the DP. In the fast version, search for the first tail strictly greater than the value (an upper bound). BinarySearch cannot promise that with duplicates, so write that loop by hand.Each item has a weight and a value. Choose a subset with total weight at most capacity that maximises total value. Each item may be taken at most once, which is the “0/1”.
best[i][w] is the maximum value using only the first i items within weight budget w.i there are exactly two options, skip it or take it:
best[i][w] = max(best[i-1][w], best[i-1][w - weight[i]] + value[i]), the second only when it fits.best[0][w] = 0. No items, no value.best[n][capacity].public static class Knapsack2D
{
/// <summary>Maximum value from a subset of items fitting inside capacity.</summary>
/// <param name="weights">Positive item weights.</param>
/// <param name="values">Item values, same length as weights.</param>
/// <param name="capacity">Maximum total weight, capacity >= 0.</param>
/// <returns>The best achievable total value.</returns>
/// <exception cref="ArgumentException">If the two arrays differ in length.</exception>
/// <example><c>Max([1, 3, 4, 5], [1, 4, 5, 7], 7)</c> returns 9.</example>
public static int Max(int[] weights, int[] values, int capacity)
{
if (weights.Length != values.Length)
{
throw new ArgumentException("weights and values must have the same length");
}
int n = weights.Length;
// best[i, room]: max value from the first i items within budget room.
// n + 1 rows: row 0 is "no items". capacity + 1 columns: rooms 0..capacity.
// A rectangular int[,] starts all 0: no items, or no room, is worth 0.
var best = new int[n + 1, capacity + 1];
// i counts the items considered. Start at 1: row 0 is the base row.
// i <= n so that item n is included.
// Invariant: row i - 1 is complete when the pass for i starts.
for (int i = 1; i <= n; i++)
{
// i - 1: item number i sits at array index i - 1.
int weight = weights[i - 1], value = values[i - 1];
// room is every budget, 0 up to capacity inclusive.
for (int room = 0; room <= capacity; room++)
{
// Skip item i: same value as the first i - 1 items in the same room.
int skip = best[i - 1, room];
if (weight <= room) // item fits in this budget
{
// Take it: best of the first i - 1 items in the leftover room.
int take = best[i - 1, room - weight] + value;
best[i, room] = Math.Max(skip, take);
}
else
{
best[i, room] = skip; // too heavy, so skip is the only option
}
}
}
// All n items considered, full budget.
return best[n, capacity];
}
}
public static class Knapsack
{
/// <summary>
/// Same answer in O(capacity) space. Row i depends only on row i - 1, so one
/// array is enough. The inner loop must run BACKWARDS, so best[room - weight]
/// still holds the previous item's value. That enforces "each item at most once".
/// </summary>
/// <param name="weights">Positive item weights.</param>
/// <param name="values">Item values, same length as weights.</param>
/// <param name="capacity">Maximum total weight, capacity >= 0.</param>
/// <returns>The best achievable total value.</returns>
/// <exception cref="ArgumentException">If the two arrays differ in length.</exception>
/// <example><c>Max([1, 3, 4, 5], [1, 4, 5, 7], 7)</c> returns 9.</example>
public static int Max(int[] weights, int[] values, int capacity)
{
if (weights.Length != values.Length)
{
throw new ArgumentException("weights and values must have the same length");
}
// best[room]: max value within budget room. +1 so room = capacity exists.
// new int[] starts at 0: before any item, every budget is worth 0.
var best = new int[capacity + 1];
// k walks the items. Python's zip becomes a plain index here.
// Invariant: at the top of each pass, best is the row for items 0..k-1.
for (int k = 0; k < weights.Length; k++)
{
int weight = weights[k], value = values[k];
// Walk room down from capacity to weight, inclusive. room-- runs
// backwards, so each item is used at most once.
for (int room = capacity; room >= weight; room--)
{
// Skip (keep best[room]) or take (previous item's best[room - weight],
// plus this value).
best[room] = Math.Max(best[room], best[room - weight] + value);
}
}
// Full budget, every item considered.
return best[capacity];
}
}
best[room - weight] after it had already been updated for the current item, so the same item could be taken twice. Backwards, every cell you read is still from the previous item’s row. Reverse the direction and you have solved the unbounded knapsack instead, where unlimited copies are allowed. One loop direction, two classic problems. That is the sentence to have ready.weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7. The optimum takes items 2 and 3, weights 3 + 4 = 7 and values 4 + 5 = 9. Taking item 4 alone gives 7. Items 1 and 4 give 1 + 7 = 8 at weight 6. So the answer is 9.
Reading the figure. Each cell is best[i][w]. A straight down arrow means skip, so the value copies from the row above. A slanted arrow means take, so it comes from w - weight columns to the left, plus the item’s value. Amber cells are the trace from the answer back to the base row. The red dashed arrow is the losing take of item 4, worth only 8.
capacity, but the input only needs log(capacity) bits to write down, so it is exponential in the input size. Knapsack is NP-hard, and this table does not contradict that. Being able to say this is a strong differentiator. Most candidates cannot.total / 2 and weight equal to value.capacity == 0: returns 0.0.room >= weight fails at once, so it is skipped.ArgumentException rather than read past the end.Given an integer array that may contain negatives, return the largest sum of any non-empty contiguous subarray.
i” state as Longest Increasing Subsequence.ending[i] is the largest sum of a subarray that ends exactly at index i.i either extends the best one ending at i - 1 or starts fresh at i, so ending[i] = max(nums[i], ending[i - 1] + nums[i]).ending[0] = nums[0].i.max(ending), because the best subarray can end anywhere. Track it as you go.public static class Kadane
{
/// <summary>Largest sum of any non-empty contiguous subarray (Kadane).</summary>
/// <param name="nums">Integers, may be negative, with at least one element.</param>
/// <returns>The maximum subarray sum.</returns>
/// <exception cref="ArgumentException">If nums is empty.</exception>
/// <example>
/// <c>MaxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])</c> returns 6.
/// <c>MaxSubarray([-3, -1, -2])</c> returns -1.
/// </example>
public static int MaxSubarray(int[] nums)
{
// The answer must be a non-empty subarray, so an empty input has none.
if (nums.Length == 0)
{
throw new ArgumentException("nums must be non-empty", nameof(nums));
}
// Two-variable state instead of a table:
// endingHere = best sum of a subarray that ENDS at the current index.
// best = best sum of any subarray seen so far.
// nums[0]: index 0 is the first element. The only subarray ending there
// is [nums[0]], so both variables start at it.
int endingHere = nums[0], best = nums[0];
// i starts at 1, because index 0 seeded both variables.
// Invariant: endingHere is the best sum ending at index i - 1,
// and best is the best sum over every subarray seen so far.
for (int i = 1; i < nums.Length; i++)
{
// Extend the run that ended one step back, or start fresh at nums[i].
// Fresh wins exactly when the old run is negative and only drags.
endingHere = Math.Max(nums[i], endingHere + nums[i]);
// The best subarray can end anywhere, so keep a running maximum.
best = Math.Max(best, endingHere);
}
return best;
}
}
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
ending_here = best = -2.1: fresh 1 beats -2 + 1. ending 1, best 1.-3: extend to -2. best stays 1.4: fresh 4 beats -2 + 4. ending 4, best 4.-1, 2, 1: extend to 3, 5, 6. best 6.-5, 4: ending drops to 1, then 5. best stays 6, from [4, -1, 2, 1].Reading the figure. Read the columns left to right. The middle row is ending_here. Amber marks a fresh start, where the number alone beats extending. That happens at 1 and at 4. Blue cells extend the run. The bottom row is best, the largest ending seen so far. It peaks at 6, in green, and never drops after that.
[-3, -1, -2]: the answer is the largest single element, -1. Seeding with 0 instead of nums[0] would wrongly return 0.ArgumentException.best improves.ints can overflow. Switch both variables to long if the constraints allow it.Given two strings, return the length of their longest common subsequence: letters that appear in both, in the same order, not necessarily next to each other. "ace" is a common subsequence of "abcde" and "ace".
table[i][j] is the LCS length of the first i letters of text1 and the first j letters of text2.table[i-1][j-1] + 1. Otherwise drop one last letter or the other: max(table[i-1][j], table[i][j-1]).0. An empty prefix shares nothing.table[text1.Length, text2.Length].public static class Lcs2D
{
/// <summary>Length of the longest common subsequence of two strings.</summary>
/// <param name="text1">First string.</param>
/// <param name="text2">Second string.</param>
/// <returns>The length of the longest subsequence present in both strings.</returns>
/// <example>
/// <c>Length("abcde", "ace")</c> returns 3. <c>Length("abc", "def")</c> returns 0.
/// </example>
public static int Length(string text1, string text2)
{
int rows = text1.Length, cols = text2.Length;
// table[i, j]: LCS length of text1[..i] and text2[..j].
// +1 on both sides so row 0 and column 0 exist: the empty prefixes.
// int[,] starts all 0: an empty prefix shares nothing.
var table = new int[rows + 1, cols + 1];
// i and j count letters used from each string. Start at 1: 0 is the base.
// <= rows and <= cols so the full strings are included.
// Invariant: every row above i is final, and so is row i left of column j.
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= cols; j++)
{
// - 1: a prefix of length i ends with the letter at index i - 1.
if (text1[i - 1] == text2[j - 1])
{
// Match: use both letters. Diagonal answer, + 1 for this letter.
table[i, j] = table[i - 1, j - 1] + 1;
}
else
{
// No match: drop text1's last letter (above, i - 1)
// or text2's last letter (left, j - 1). Keep the better.
table[i, j] = Math.Max(table[i - 1, j], table[i, j - 1]);
}
}
}
// Both full strings.
return table[rows, cols];
}
}
public static class LcsRolling
{
/// <summary>Same answer in O(text2.Length) space, keeping only two rows.</summary>
/// <param name="text1">First string. Its letters drive the rows.</param>
/// <param name="text2">Second string. Its letters are the columns.</param>
/// <returns>The length of the longest subsequence present in both strings.</returns>
/// <example><c>Length("abcde", "ace")</c> returns 3.</example>
public static int Length(string text1, string text2)
{
int cols = text2.Length;
// previous is the row above. It starts as row 0: empty text1 prefix, all 0.
// cols + 1: +1 so slot cols exists. Slot 0 is the empty text2 prefix.
var previous = new int[cols + 1];
// One row per letter of text1.
// Invariant: previous holds the finished row for the letters before this one.
foreach (char letter in text1)
{
// Fresh row. Slot 0 stays 0: an empty text2 prefix shares nothing.
var current = new int[cols + 1];
// j counts text2 letters. Start at 1: slot 0 is the base.
// j <= cols so the last letter is included.
for (int j = 1; j <= cols; j++)
{
// j - 1: the j-th letter of text2 sits at index j - 1.
if (letter == text2[j - 1])
{
// Match: diagonal (previous[j - 1]) + 1 for this letter.
current[j] = previous[j - 1] + 1;
}
else
{
// No match: best of above (previous[j]) and left (current[j - 1]).
current[j] = Math.Max(previous[j], current[j - 1]);
}
}
// Row done. It becomes the row above for the next letter.
previous = current;
}
// Last row, last slot: both full strings.
return previous[cols];
}
}
This is Template C with combine filled in. The diagonal cell previous[j - 1] is why you need two rows here. Reading it from a single row would see a value already overwritten for this row.
text1 = "abcde", text2 = "ace". Each bullet is one row, for "" a c e:
a: 0 1 1 1. The a matches, and the 1 carries right.b: 0 1 1 1. No match, so values copy down.c: 0 1 2 2. The c matches: diagonal 1, plus 1.d: 0 1 2 2. No match.e: 0 1 2 3. The e matches: diagonal 2, plus 1. Answer 3.Reading the figure. Rows are prefixes of "abcde" and columns are prefixes of "ace". Each amber cell is a letter match, and its green arrow shows it reading the diagonal and adding 1. Blue cells copy the larger of the cell above and the cell to the left. Follow the three green arrows from the top left to the corner. They spell out a, c, e.
0, straight from the base row or column.0.O(min(m, n)) space.Return the fewest single-letter operations that turn word1 into word2. The allowed operations are insert a letter, delete a letter, and replace a letter. This is the Levenshtein distance.
table[i][j] is the fewest edits to turn the first i letters of word1 into the first j letters of word2.table[i-1][j-1]. Otherwise pay 1 and take the cheapest of delete (table[i-1][j]), insert (table[i][j-1]), or replace (table[i-1][j-1]).table[i][0] = i, which is i deletes. table[0][j] = j, which is j inserts.table[word1.Length, word2.Length].public static class EditDistance
{
/// <summary>Fewest inserts, deletes, or replaces that turn word1 into word2.</summary>
/// <param name="word1">Source string.</param>
/// <param name="word2">Target string.</param>
/// <returns>The edit (Levenshtein) distance.</returns>
/// <example>
/// <c>MinEdits("horse", "ros")</c> returns 3. <c>MinEdits("", "abc")</c> returns 3.
/// </example>
public static int MinEdits(string word1, string word2)
{
int rows = word1.Length, cols = word2.Length;
// table[i, j]: fewest edits to turn word1[..i] into word2[..j].
// +1 on both sides so row 0 and column 0 (the empty prefixes) exist.
// The 0s from new are placeholders. The loops below overwrite every cell.
var table = new int[rows + 1, cols + 1];
// Base column: turning i letters into "" takes i deletes.
// i <= rows so that i = rows is included.
for (int i = 0; i <= rows; i++)
{
table[i, 0] = i;
}
// Base row: turning "" into j letters takes j inserts.
// j <= cols so that j = cols is included.
for (int j = 0; j <= cols; j++)
{
table[0, j] = j;
}
// Start at 1: row 0 and column 0 are the base cases above.
// Invariant: every row above i is final, and so is row i left of column j.
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= cols; j++)
{
// - 1: a prefix of length i ends with the letter at index i - 1.
if (word1[i - 1] == word2[j - 1])
{
// Last letters already match: no edit, take the diagonal.
table[i, j] = table[i - 1, j - 1];
}
else
{
// 1 for the edit made now, plus the cheapest smaller case.
table[i, j] = 1 + Math.Min(
table[i - 1, j], // delete word1's letter (above)
Math.Min(
table[i, j - 1], // insert word2's letter (left)
table[i - 1, j - 1])); // replace (diagonal)
}
}
}
// Both full words.
return table[rows, cols];
}
}
word1 = "horse", word2 = "ros". The table ends at 3. One optimal path:
h with r: horse becomes rorse.r: rorse becomes rose.e: rose becomes ros.table[5][0] = 5, because turning "horse" into "" takes five deletes.Reading the figure. Rows are prefixes of "horse" and columns are prefixes of "ros". Grey cells are the base row and column, pure inserts or deletes. The amber cells and arrows are one cheapest path. A diagonal step is a replace, or free when the letters match. A down step is a delete. The cost rises by 1 only on the three edit steps, and ends at 3 in the green corner.
0, all diagonal moves.0, 1, ..., n, and each new row starts with its row number in slot 0.1 with that operation’s cost. The shape stays the same.m + n - 2 × LCS. Saying that ties the two problems together.i”.Dictionary or array memo. Then tabulate. Then compress.int.MaxValue + 1 overflows, counts need long, and deep recursion can overflow the 1 MB stack.That closes the four classical parts. Part V adds the four patterns these pages keep pointing at without covering. First is Pattern 13, Prefix Sum and Hash Map, which handles exactly the case the sliding window has to give up on.