DYNAMIC PROGRAMMING

Short Notes Handbook

Based on Aditya Verma's Dynamic Programming YouTube Playlist

Covers every problem in playlist order — Recursion, Memoization, Tabulation, Recognition patterns, Recurrence relations,
C++17 code, Complexity, and Interview notes.

For SDE Interview & Placement Preparation

Table of Contents
TOC \h \o "1-2"
How to Use This Handbook
This handbook gives short, exam-ready notes for every problem in Aditya Verma's Dynamic Programming playlist, in
playlist order, grouped by pattern. Each entry contains: the problem statement, how to recognize the pattern, the
recurrence relation, working C++17 code, time/space complexity, and common mistakes/interview notes.

Use it for quick revision before interviews: read the 'Recognize It' and 'Recurrence Relation' boxes for every problem
in one pass, then re-derive the code from memory and check it against the printed solution.
Chapter 0 — Foundations of Dynamic Programming
Before solving any DP problem, understand these four pillars: recursion (brute force), overlapping subproblems,
optimal substructure, and state. Every problem in this playlist is solved using the same five-step method taught by
Aditya Verma: (1) write the recursive brute force, (2) identify what changes between calls — that becomes your state,
(3) memoize with an array/map keyed on that state, (4) convert to a bottom-up table, (5) optimize space if only a few
previous rows/states are needed.

0.1 What is Dynamic Programming?

Problem:
DP is not a separate algorithm — it is plain recursion where we avoid recomputing answers to the same subproblem.
If a recursive solution recomputes identical (state) values many times, DP simply stores the first answer and reuses it.

How to Recognize It
• Overlapping subproblems: the same recursive call is made with identical parameters more than once.
• Optimal substructure: the optimal answer to the problem can be built from optimal answers to its subproblems.
• State: the minimal set of changing parameters that uniquely identifies a subproblem.

Recurrence Relation
No single formula — but every DP problem reduces to: solve(state) = combine( solve(smaller
state 1), solve(smaller state 2), ... )

Complexity: N/A — conceptual chapter.

Common Mistakes & Interview Notes

• Recursion answers 'what is the answer for this exact input?' — DP answers it once and remembers it.
• If you cannot draw the recursion tree with repeating nodes, it is not a DP problem — plain recursion or greedy
may suffice.

0.2 Recursion → Memoization → Tabulation → Space Optimization

Problem:
The four stages every DP solution passes through, in increasing order of efficiency.

How to Recognize It
• Recursion: exponential time, no extra memory beyond the call stack — correct but slow.
• Memoization (top-down): add a lookup table; before computing, check if state was already solved.
• Tabulation (bottom-up): remove recursion entirely, fill the table iteratively from base cases upward.
• Space optimization: if row i only depends on row i-1 (or a constant number of previous states), keep only those
rows.
C++17 Solution
// Generic template pattern used throughout this handbook

// 1) Recursion
int solveRec(/* state */) {
// base case
// choices -> recursive calls -> combine
}

// 2) Memoization
vector<vector<int>> dp(N+1, vector<int>(M+1, -1));
int solveMemo(/* state */) {
// base case
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = /* recursive relation */;
}

// 3) Tabulation
vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
// initialize base cases in dp[][]
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
dp[i][j] = /* same relation, using dp[i-1][..] etc. */;

// 4) Space optimization
vector<int> prev(M+1, 0), curr(M+1, 0);
// loop as above, swap(prev, curr) at the end of each outer iteration

Complexity: Recursion: exponential. Memoization/Tabulation: O(states × transition cost). Space-optimized: O(one or

two rows).

Common Mistakes & Interview Notes

• Always write the recursive solution first — even in an interview. It proves you understand the problem before
optimizing.
• Memoization and tabulation always have the *same* time and space complexity for the table; only the space-
optimized version differs.
Chapter 1 — 0/1 Knapsack Pattern
The 0/1 Knapsack pattern applies whenever you must choose a subset of items — each used at most once — to
satisfy or optimize a target capacity/sum. Recognize it by: 'array of items + a target value/capacity + include-or-
exclude choice'.

1.1 0/1 Knapsack

Problem:
Given weights[] and values[] of n items and a knapsack of capacity W, choose items (each usable once) to maximize
total value without exceeding W.
Input: weights[], values[], W. Output: maximum achievable value.

How to Recognize It
• State: (index i, remaining capacity j) — these are the only two things that change between recursive calls.
• Choice at each item: include it (if it fits) or exclude it.
• Overlapping subproblems: many different item orders lead to the same (i, remaining capacity) pair.

Recurrence Relation
knapsack(i, j) = max( values[i] + knapsack(i-1, j-weights[i]) [if weights[i] <= j],
knapsack(i-1, j) )
Base case: knapsack(0, j) = 0 or knapsack(i, 0) = 0

C++17 Solution
int knapsack(vector<int>& wt, vector<int>& val, int n, int W) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int cap = 1; cap <= W; cap++) {
int exclude = dp[i - 1][cap];
int include = (wt[i - 1] <= cap)
? val[i - 1] + dp[i - 1][cap - wt[i - 1]]
: 0;
dp[i][cap] = max(include, exclude);
}
}
return dp[n][W];
}

Complexity: Recursion: O(2^n). Memoization/Tabulation: O(n*W) time, O(n*W) space. Space-optimized (1-D array,
iterate capacity right-to-left): O(W) space.

Common Mistakes & Interview Notes

• Common mistake: iterating capacity left-to-right in the space-optimized 1-D version, which corrupts results (that
pattern is only valid for Unbounded Knapsack).
 • Common mistake: sizing the dp array as (n, W) instead of (n+1, W+1) and losing the base-case row/column.
• Similar: Subset Sum, Partition Equal Subset Sum, Target Sum, Coin Change II — all reuse this exact template with a
different 'combine' step.

1.2 Subset Sum Problem

Problem:
Given an array of non-negative integers and a target sum, determine whether any subset sums exactly to the target.
Output: boolean.

How to Recognize It
• Identical to 0/1 Knapsack with 'value' removed — we only track whether a sum is reachable, not an optimal
value.
• State: (index i, remaining sum j).

Recurrence Relation
isSubsetSum(i, j) = isSubsetSum(i-1, j) OR (arr[i] <= j AND isSubsetSum(i-1, j-arr[i]))
Base case: isSubsetSum(i, 0) = true; isSubsetSum(0, j>0) = false

C++17 Solution
bool subsetSum(vector<int>& arr, int n, int target) {
vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
for (int i = 0; i <= n; i++) dp[i][0] = true; // sum 0 always achievable
for (int i = 1; i <= n; i++) {
for (int s = 1; s <= target; s++) {
dp[i][s] = dp[i - 1][s];
if (arr[i - 1] <= s) dp[i][s] = dp[i][s] || dp[i - 1][s - arr[i - 1]];
}
}
return dp[n][target];
}

Complexity: O(n*target) time and space; O(target) with 1-D space optimization.

Common Mistakes & Interview Notes

• LeetCode 416 (Partition Equal Subset Sum) is this problem with target = totalSum/2.
• Watch for odd totalSum: if totalSum is odd, equal partition is impossible — return false immediately.

1.3 Equal Sum Partition

Problem:
Determine whether an array can be split into two subsets with equal sum. (LeetCode 416)
How to Recognize It
• Direct reduction to Subset Sum with target = totalSum / 2.

Recurrence Relation
Same as Subset Sum, with target = sum(arr) / 2.

C++17 Solution
bool canPartition(vector<int>& nums) {
int total = accumulate([Link](), [Link](), 0);
if (total % 2 != 0) return false;
return subsetSum(nums, [Link](), total / 2);
}

Complexity: O(n*sum) time, O(sum) space optimized.

Common Mistakes & Interview Notes

• Always check the parity of the total sum before running the DP — a cheap early exit.

1.4 Count of Subsets with a Given Sum

Problem:
Count how many subsets of an array sum exactly to a given target.

How to Recognize It
• Same state as Subset Sum, but the combine step adds counts instead of OR-ing booleans.

Recurrence Relation
countSS(i, j) = countSS(i-1, j) + (arr[i]<=j ? countSS(i-1, j-arr[i]) : 0)
Base case: countSS(i, 0) = 1 for all i (empty subset). If arr contains zeros, countSS(0,0)
needs special handling (multiply by 2 per zero).

C++17 Solution
int countSubsetSum(vector<int>& arr, int n, int target) {
vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int s = 0; s <= target; s++) {
dp[i][s] = dp[i - 1][s];
if (arr[i - 1] <= s) dp[i][s] += dp[i - 1][s - arr[i - 1]];
}
return dp[n][target];
}
 Complexity: O(n*target) time and space.

Common Mistakes & Interview Notes

• Beginner mistake: forgetting that zeros in the array double the count of every subset that includes them.
• GFG 'Perfect Sum Problem' requires the answer modulo 1e9+7 — remember to add the mod.

1.5 Minimum Subset Sum Difference

Problem:
Partition array into two subsets S1 and S2 minimizing |sum(S1) - sum(S2)|.

How to Recognize It
• Run Subset Sum DP once for target = totalSum, keeping the full boolean row for i = n.
• Every reachable sum s in [0, totalSum/2] gives a valid partition value; the answer is min(totalSum - 2*s) over
reachable s.

Recurrence Relation
Reuses Subset Sum table; answer = min over s in [0, sum/2] where dp[n][s] is true of (sum
- 2*s).

C++17 Solution
int minSubsetSumDiff(vector<int>& arr, int n) {
int total = accumulate([Link](), [Link](), 0);
vector<vector<bool>> dp(n + 1, vector<bool>(total + 1, false));
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++)
for (int s = 0; s <= total; s++) {
dp[i][s] = dp[i - 1][s];
if (arr[i - 1] <= s) dp[i][s] = dp[i][s] || dp[i - 1][s - arr[i - 1]];
}
int best = INT_MAX;
for (int s = 0; s <= total / 2; s++)
if (dp[n][s]) best = min(best, total - 2 * s);
return best;
}

Complexity: O(n*totalSum) time and space.

Common Mistakes & Interview Notes

• Only scan s up to totalSum/2 — sums beyond that mirror sums already checked.

1.6 Count of Subsets with a Given Difference

Problem:
Count subsets S1, S2 partitioning the array such that sum(S1) - sum(S2) = diff.

How to Recognize It
• Algebra: S1 + S2 = totalSum and S1 - S2 = diff => S1 = (totalSum + diff) / 2.
• Reduces exactly to Count of Subsets with a Given Sum, target = (totalSum + diff)/2.

Recurrence Relation
target = (total + diff) / 2; answer = countSubsetSum(arr, n, target)

C++17 Solution
int countSubsetsGivenDiff(vector<int>& arr, int n, int diff) {
int total = accumulate([Link](), [Link](), 0);
if ((total + diff) % 2 != 0 || total < diff) return 0; // no valid partition
return countSubsetSum(arr, n, (total + diff) / 2);
}

Complexity: O(n*total) time and space.

Common Mistakes & Interview Notes

• Common mistake: not checking (total+diff) is even before dividing by 2 — leads to silently wrong (truncated)
targets.
• This trick — translating a 'difference' constraint into a 'sum' target — reappears often in interviews.

1.7 Target Sum (LeetCode 494)

Problem:
Assign a '+' or '-' sign to each number in an array so the resulting expression evaluates to a given target; count the
number of ways.

How to Recognize It
• Identical to Count of Subsets with Given Difference: positive-signed numbers form S1, negative-signed form S2,
and S1 - S2 = target.

Recurrence Relation
Same as 1.6 with diff = target.

C++17 Solution
int findTargetSumWays(vector<int>& nums, int target) {
int n = [Link]();
return countSubsetsGivenDiff(nums, n, target);
}
Complexity: O(n*total) time and space.

Common Mistakes & Interview Notes

• Interviewers often ask this cold to see if you can recognize the reduction without being told it is a Knapsack
variant.
Chapter 2 — Unbounded Knapsack Pattern
Unbounded Knapsack differs from 0/1 Knapsack in exactly one place: an item may be reused unlimited times.
Recognize it by phrases like 'unlimited supply', 'as many times as needed', or 'rod pieces/coins can repeat'.

2.1 Unbounded Knapsack

Problem:
Same as 0/1 Knapsack, but each item can be picked any number of times. Maximize value within capacity W.

How to Recognize It
• State is still (i, capacity), but the 'include' branch stays on the same row i (not i-1) because the item can be
reused.

Recurrence Relation
dp(i, j) = max( val[i] + dp(i, j-wt[i]) [if wt[i]<=j], dp(i-1, j) )

C++17 Solution
int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++)
for (int cap = 1; cap <= W; cap++) {
int exclude = dp[i - 1][cap];
int include = (wt[i - 1] <= cap)
? val[i - 1] + dp[i][cap - wt[i - 1]] // stay on row i
: 0;
dp[i][cap] = max(include, exclude);
}
return dp[n][W];
}

Complexity: O(n*W) time, O(n*W) space; O(W) space optimized (single 1-D row, iterate capacity left-to-right).

Common Mistakes & Interview Notes

• The ONLY code difference from 0/1 Knapsack is `dp[i]` instead of `dp[i-1]` in the include branch — a favorite
interview follow-up question.

2.2 Rod Cutting

Problem:
Given a rod of length n and a price array price[] for each length 1..n, cut the rod into pieces to maximize total
revenue.
How to Recognize It
• 'length' plays the role of weight, 'price' plays the role of value, and each cut length may be used unlimited times
— pure Unbounded Knapsack.

Recurrence Relation
length[i] = i+1 (1-indexed lengths); reuse Unbounded Knapsack with wt=length, val=price,
W=n.

C++17 Solution
int rodCutting(vector<int>& price, int n) {
vector<int> length(n);
for (int i = 0; i < n; i++) length[i] = i + 1;
return unboundedKnapsack(length, price, n, n);
}

Complexity: O(n^2) time, O(n) space optimized.

Common Mistakes & Interview Notes

• Classic beginner mistake: assuming pieces must be cut only once — re-read the problem; any length can repeat.

2.3 Coin Change — Maximum Number of Ways

Problem:
Given coin denominations and a target amount, count the number of ways to make that amount (order does not
matter). (LeetCode 518 'Coin Change II')

How to Recognize It
• Unbounded Knapsack 'combine' step becomes addition of ways instead of max of value.

Recurrence Relation
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]] [if coins[i-1] <= j]
Base case: dp[i][0] = 1 for all i.

C++17 Solution
int coinChangeWays(vector<int>& coins, int amount) {
int n = [Link]();
vector<vector<long long>> dp(n + 1, vector<long long>(amount + 1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int a = 1; a <= amount; a++) {
dp[i][a] = dp[i - 1][a];
if (coins[i - 1] <= a) dp[i][a] += dp[i][a - coins[i - 1]];
}
return (int)dp[n][amount];
 }

Complexity: O(n*amount) time and space; O(amount) space optimized.

Common Mistakes & Interview Notes

• Iterating coins in the outer loop and amount in the inner loop (as above) avoids counting permutations as distinct
— critical for correctness.

2.4 Coin Change — Minimum Number of Coins

Problem:
Given coin denominations and a target amount, find the minimum number of coins needed to make that amount, or -
1 if impossible. (LeetCode 322)

How to Recognize It
• Same state, but combine step takes the minimum count and adds 1 coin when included.

Recurrence Relation
dp[i][j] = min( dp[i-1][j], 1 + dp[i][j-coins[i-1]] )
Base case: dp[i][0] = 0; dp[0][j>0] = INF (unreachable with zero coin types).

C++17 Solution
int coinChangeMin(vector<int>& coins, int amount) {
int n = [Link]();
const int INF = 1e9;
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));
for (int i = 0; i <= n; i++) dp[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int a = 1; a <= amount; a++) {
dp[i][a] = dp[i - 1][a];
if (coins[i - 1] <= a)
dp[i][a] = min(dp[i][a], 1 + dp[i][a - coins[i - 1]]);
}
return dp[n][amount] >= INF ? -1 : dp[n][amount];
}

Complexity: O(n*amount) time and space.

Common Mistakes & Interview Notes

• Initialize with a large sentinel (INF), not INT_MAX, to avoid overflow when adding 1.
Chapter 3 — Longest Common Subsequence (LCS) Pattern
The LCS pattern applies to problems comparing two strings/sequences. Recognize it by two pointers i (end of string A)
and j (end of string B); the two universal moves are 'characters match → advance both' and 'characters differ → try
skipping one'.

3.1 Longest Common Subsequence

Problem:
Given two strings s1 (length n) and s2 (length m), find the length of their longest common subsequence (characters in
relative order, not necessarily contiguous). (LeetCode 1143)

How to Recognize It
• State: (i, j) = lengths of prefixes of s1 and s2 still being considered.
• Optimal substructure: LCS of full strings depends only on LCS of shorter prefixes.

Recurrence Relation
lcs(i,j) = 1 + lcs(i-1,j-1) if s1[i-1]==s2[j-1]
lcs(i,j) = max(lcs(i-1,j), lcs(i,j-1)) otherwise
Base case: lcs(0,j)=lcs(i,0)=0

C++17 Solution
int lcs(string& s1, string& s2) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (s1[i - 1] == s2[j - 1])
? 1 + dp[i - 1][j - 1]
: max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][m];
}

Complexity: O(n*m) time and space; O(min(n,m)) space optimized.

Common Mistakes & Interview Notes

• Off-by-one indexing (dp uses 1-indexed rows/cols but the strings are 0-indexed) is the #1 beginner bug in this
whole pattern.
• This is the foundation problem for nearly every other item in this chapter.

3.2 Longest Common Substring

Problem:
Find the length of the longest common *contiguous* substring between two strings (not a subsequence).

How to Recognize It
• Same (i,j) state as LCS, but a mismatch resets the running length to 0 instead of taking a max.

Recurrence Relation
dp(i,j) = 1 + dp(i-1,j-1) if s1[i-1]==s2[j-1]
dp(i,j) = 0 otherwise
Answer = max value anywhere in the dp table (not necessarily dp[n][m]).

C++17 Solution
int longestCommonSubstring(string& s1, string& s2) {
int n = [Link](), m = [Link](), best = 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
best = max(best, dp[i][j]);
}
// else dp[i][j] stays 0 (contiguity breaks)
}
return best;
}

Complexity: O(n*m) time and space.

Common Mistakes & Interview Notes

• Beginner mistake: copying the LCS max(dp[i-1][j], dp[i][j-1]) into the mismatch branch — that turns this back into
subsequence, not substring.

3.3 Printing the LCS

Problem:
Given two strings, output the actual longest common subsequence string, not just its length.

How to Recognize It
• Build the standard LCS dp table first, then walk backwards from dp[n][m] following the same decisions that built
the table.

Recurrence Relation
Backtrack from (n, m): if s1[i-1]==s2[j-1], append char, move to (i-1,j-1); else move
toward whichever of dp[i-1][j], dp[i][j-1] is larger.
C++17 Solution
string printLCS(string& s1, string& s2) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (s1[i-1]==s2[j-1]) ? 1+dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]);

string result;
int i = n, j = m;
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) { result += s1[i - 1]; i--; j--; }
else if (dp[i - 1][j] > dp[i][j - 1]) i--;
else j--;
}
reverse([Link](), [Link]());
return result;
}

Complexity: O(n*m) time and space (table must be fully materialized — space cannot be optimized away here).

Common Mistakes & Interview Notes

• This is why space optimization is skipped for 'printing' variants — you need the whole table to backtrack.

3.4 Shortest Common Supersequence (SCS) — length

Problem:
Find the length of the shortest string that has both s1 and s2 as subsequences. (LeetCode 1092 for the string variant)

How to Recognize It
• SCS length = n + m − LCS(s1, s2): keep every character of both strings, but do not duplicate the shared
subsequence.

Recurrence Relation
scsLength = n + m - lcs(s1, s2)

C++17 Solution
int shortestCommonSupersequenceLength(string& s1, string& s2) {
int n = [Link](), m = [Link]();
return n + m - lcs(s1, s2);
}

Complexity: O(n*m) time and space (dominated by the LCS computation).

 Common Mistakes & Interview Notes
• Interviewers love asking 'why does this formula work?' — because every character not in the LCS must appear
exactly once, and every LCS character is shared once.

3.5 Printing the Shortest Common Supersequence

Problem:
Construct the actual shortest common supersequence string of s1 and s2.

How to Recognize It
• Backtrack through the LCS table like 3.3, but when characters differ, emit the character belonging to whichever
pointer we move, and when they match, emit it once.

Recurrence Relation
Same backtracking walk as Printing LCS, but append every visited character (matched or
not) instead of skipping mismatches.

C++17 Solution
string printSCS(string& s1, string& s2) {
int n = [Link](), m = [Link]();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (s1[i-1]==s2[j-1]) ? 1+dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]);

string result;
int i = n, j = m;
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) { result += s1[i - 1]; i--; j--; }
else if (dp[i - 1][j] > dp[i][j - 1]) { result += s1[i - 1]; i--; }
else { result += s2[j - 1]; j--; }
}
while (i > 0) { result += s1[i - 1]; i--; }
while (j > 0) { result += s2[j - 1]; j--; }
reverse([Link](), [Link]());
return result;
}

Complexity: O(n*m) time and space.

Common Mistakes & Interview Notes

• Do not forget the two trailing while-loops — they flush any leftover prefix once one pointer reaches 0.

3.6 Minimum Insertions and Deletions to Convert String A to String B

Problem:
Find the minimum number of insert and delete operations to transform s1 into s2.

How to Recognize It
• Keep the LCS (the common part) untouched; delete everything else from s1 and insert everything else from s2.

Recurrence Relation
deletions = n - lcs(s1,s2)
insertions = m - lcs(s1,s2)

C++17 Solution
pair<int,int> minInsertDelete(string& s1, string& s2) {
int n = [Link](), m = [Link]();
int l = lcs(s1, s2);
int deletions = n - l;
int insertions = m - l;
return {deletions, insertions};
}

Complexity: O(n*m) time and space.

Common Mistakes & Interview Notes

• GFG variant asks for total operations (deletions + insertions); LeetCode 583 asks only for deletions.

3.7 Longest Palindromic Subsequence (LPS)

Problem:
Given a string s, find the length of its longest subsequence that is also a palindrome. (LeetCode 516)

How to Recognize It
• A palindromic subsequence of s is exactly the LCS of s and reverse(s).

Recurrence Relation
lps(s) = lcs(s, reverse(s))

C++17 Solution
int longestPalindromicSubsequence(string& s) {
string rev = s;
reverse([Link](), [Link]());
return lcs(s, rev);
}

Complexity: O(n^2) time and space (n = [Link]()).

 Common Mistakes & Interview Notes
• A cleaner interval-DP formulation also exists (dp[i][j] = 2+dp[i+1][j-1] if s[i]==s[j]) but the LCS reduction is faster to
derive under interview pressure.

3.8 Minimum Deletions to Make a String Palindrome

Problem:
Find the minimum number of character deletions needed to make a string a palindrome.

How to Recognize It
• Whatever isn't part of the Longest Palindromic Subsequence must be deleted.

Recurrence Relation
minDeletions = n - lps(s)

C++17 Solution
int minDeletionsToPalindrome(string& s) {
return [Link]() - longestPalindromicSubsequence(s);
}

Complexity: O(n^2) time and space.

Common Mistakes & Interview Notes

• Directly reuses 3.7 — a good example of how the LCS/LPS pattern chains together.

3.9 Minimum Insertions to Make a String Palindrome

Problem:
Find the minimum number of character insertions needed to make a string a palindrome. (LeetCode 1312)

How to Recognize It
• Symmetric to 3.8: characters not part of the LPS need a mirrored insertion.

Recurrence Relation
minInsertions = n - lps(s)

C++17 Solution
int minInsertionsToPalindrome(string& s) {
 return [Link]() - longestPalindromicSubsequence(s);
}

Complexity: O(n^2) time and space.

Common Mistakes & Interview Notes

• Numerically identical formula to Minimum Deletions — but conceptually different operations; interviewers ask
both to test if you understand *why* they coincide.

3.10 Longest Repeating Subsequence

Problem:
Find the length of the longest subsequence of s that appears at least twice, with the two occurrences using different
indices.

How to Recognize It
• Run LCS of s against itself, but disallow matching a character with itself at the same index (i != j).

Recurrence Relation
lrs(i,j) = 1 + lrs(i-1,j-1) if s[i-1]==s[j-1] AND i != j
lrs(i,j) = max(lrs(i-1,j), lrs(i,j-1)) otherwise

C++17 Solution
int longestRepeatingSubsequence(string& s) {
int n = [Link]();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (s[i - 1] == s[j - 1] && i != j)
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
return dp[n][n];
}

Complexity: O(n^2) time and space.

Common Mistakes & Interview Notes

• The single extra condition `i != j` is the entire difference from plain LCS — an easy detail to forget.
3.11 Sequence Pattern Matching (Is Subsequence)
Problem:
Given strings s and t, determine whether s is a subsequence of t. (LeetCode 392)

How to Recognize It
• s is a subsequence of t exactly when lcs(s, t) == [Link]().

Recurrence Relation
isSubsequence = (lcs(s, t) == [Link]())

C++17 Solution
bool isSubsequence(string s, string t) {
return lcs(s, t) == (int)[Link]();
}

Complexity: O(n*m) via LCS reduction; a linear two-pointer O(n+m) approach exists and is preferred for this exact
LeetCode problem in production code.

Common Mistakes & Interview Notes

• Mention the O(n+m) two-pointer alternative in interviews — showing you know the DP is not always the *most*
efficient tool builds credibility.

3.12 LCS of Three Strings / LeetCode Variants

Problem:
Adaptations of core LCS (e.g., LCS of 3 strings, or LCS with different output requirements) as seen in the LeetCode-
focused lecture of the series.

How to Recognize It
• Extend the state to (i, j, k) for a third string, or reuse two-string LCS directly depending on exact constraints
given.

Recurrence Relation
lcs3(i,j,k) = 1+lcs3(i-1,j-1,k-1) if all three chars match, else max over dropping one
index at a time.

C++17 Solution
int lcsOfThree(string& a, string& b, string& c) {
int n=[Link](), m=[Link](), p=[Link]();
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(p+1, 0)));
for (int i = 1; i <= n; i++)
 for (int j = 1; j <= m; j++)
for (int k = 1; k <= p; k++) {
if (a[i-1]==b[j-1] && b[j-1]==c[k-1])
dp[i][j][k] = 1 + dp[i-1][j-1][k-1];
else
dp[i][j][k] = max({dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]});
}
return dp[n][m][p];
}

Complexity: O(n*m*p) time and space.

Common Mistakes & Interview Notes

• Adding a third string always multiplies the state space by one more dimension — the recurrence logic barely
changes.
Chapter 4 — Matrix Chain Multiplication (MCM) / Partition DP Pattern
MCM-pattern (a.k.a. 'Interval DP' or 'Partition DP') problems ask you to place a 'cut point' k inside a range [i, j] and
combine the results of the two halves. Recognize it by: 'given a sequence/string, find the best way to
split/parenthesize/partition it', with a cost or count depending on where you split.

4.1 Matrix Chain Multiplication

Problem:
Given dimensions of matrices to multiply in a chain, find the minimum number of scalar multiplications needed to
compute the product, by choosing the optimal parenthesization.

How to Recognize It
• State: (i, j) representing the subrange of matrices being multiplied.
• Try every split point k between i and j; cost = cost(i,k) + cost(k+1,j) + cost of multiplying the two resulting
matrices.

Recurrence Relation
mcm(i,j) = min over k in [i, j-1] of mcm(i,k) + mcm(k+1,j) + arr[i-1]*arr[k]*arr[j]
Base case: mcm(i,i) = 0 (a single matrix needs no multiplication).

C++17 Solution
int mcmRec(vector<int>& arr, int i, int j) {
if (i >= j) return 0; // base case: single matrix
int minCost = INT_MAX;
for (int k = i; k < j; k++) {
int cost = mcmRec(arr, i, k) + mcmRec(arr, k + 1, j)
+ arr[i - 1] * arr[k] * arr[j];
minCost = min(minCost, cost);
}
return minCost;
}
// dp[i][j] memo table follows the same recurrence with a 2D cache keyed on (i, j)

Complexity: Recursion: exponential (Catalan-number growth). Memoization/Tabulation: O(n^3) time, O(n^2) space.

Common Mistakes & Interview Notes

• Common mistake: iterating i and j directly instead of by increasing 'chain length' (gap) in the tabulated version —
MCM tabulation must fill the table by interval length, not by row.
• This is the archetype for every problem in this chapter.
4.2 Minimum Cost to Cut a Stick / Burst Balloons style MCM-LeetCode variants
Problem:
LeetCode-style variants of the MCM recurrence, e.g. 'Minimum Score Triangulation of Polygon' (LeetCode 1039):
given polygon vertex values, triangulate to minimize total score.

How to Recognize It
• Same interval (i, j) state with a split point k; the 'cost' formula changes per problem but the loop skeleton is
identical to MCM.

Recurrence Relation
triangulate(i,j) = min over k in (i, j) of triangulate(i,k) + triangulate(k,j) +
values[i]*values[k]*values[j]

C++17 Solution
int minScoreTriangulation(vector<int>& values) {
int n = [Link]();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len < n; len++) {
for (int i = 0; i + len < n; i++) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k++)
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]);
}
}
return dp[0][n - 1];
}

Complexity: O(n^3) time, O(n^2) space.

Common Mistakes & Interview Notes

• Recognizing that 'polygon triangulation' is really MCM in disguise is a favorite hard-interview pattern-matching
test.

4.3 Palindrome Partitioning — Minimum Cuts (Recursive)

Problem:
Given a string, find the minimum number of cuts needed so every resulting substring is a palindrome. (LeetCode 132)

How to Recognize It
• MCM-style interval DP: for a range [i, j], try every cut point k; if s[i..k] is a palindrome, recurse on the remainder.

Recurrence Relation
minCuts(i,j) = 0 if s[i..j] is a palindrome
 minCuts(i,j) = min over k in [i, j-1] of 1 + minCuts(i,k) + minCuts(k+1,j) otherwise

C++17 Solution
bool isPalindrome(string& s, int i, int j) {
while (i < j) if (s[i++] != s[j--]) return false;
return true;
}
int minCutsRec(string& s, int i, int j) {
if (i >= j || isPalindrome(s, i, j)) return 0;
int minCost = INT_MAX;
for (int k = i; k < j; k++) {
if (isPalindrome(s, i, k)) {
int cost = 1 + minCutsRec(s, k + 1, j);
minCost = min(minCost, cost);
}
}
return minCost;
}

Complexity: Exponential without memoization; checking isPalindrome each time adds an extra O(n) factor.

Common Mistakes & Interview Notes

• Precomputing a palindrome[i][j] boolean table before the DP turns the isPalindrome check into O(1) — a critical
optimization covered next.

4.4 Palindrome Partitioning — Memoization

Problem:
Same problem as 4.3, optimized with a 2D memo table on (i, j).

How to Recognize It
• Overlapping subproblems appear because the same (i, j) range is re-examined through different cut sequences.

Recurrence Relation
Same recurrence as 4.3, cached in dp[i][j].

C++17 Solution
vector<vector<int>> memo;
int minCutsMemo(string& s, int i, int j) {
if (i >= j || isPalindrome(s, i, j)) return 0;
if (memo[i][j] != -1) return memo[i][j];
int minCost = INT_MAX;
for (int k = i; k < j; k++)
if (isPalindrome(s, i, k))
minCost = min(minCost, 1 + minCutsMemo(s, k + 1, j));
return memo[i][j] = minCost;
 }

Complexity: O(n^3) time (n^2 states × O(n) split loop), O(n^2) space.

Common Mistakes & Interview Notes

• Still calls isPalindrome() repeatedly — 4.5 removes this redundancy.

4.5 Palindrome Partitioning — Optimized with Precomputed Palindrome Table

Problem:
Same problem, but a boolean isPal[i][j] table is precomputed in O(n^2) so palindrome checks inside the DP become
O(1).

How to Recognize It
• Precompute isPal[i][j] using: isPal[i][j] = (s[i]==s[j]) AND (j-i<=2 OR isPal[i+1][j-1]).

Recurrence Relation
Same cut recurrence as 4.3/4.4, but isPalindrome(i,j) is replaced with the O(1) lookup
isPal[i][j].

C++17 Solution
int minCutsOptimized(string& s) {
int n = [Link]();
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int len = 1; len <= n; len++)
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j] && (len <= 2 || isPal[i+1][j-1])) isPal[i][j] = true;
}

vector<int> dp(n, 0); // dp[j] = min cuts for s[0..j]

for (int j = 0; j < n; j++) {
if (isPal[0][j]) { dp[j] = 0; continue; }
dp[j] = INT_MAX;
for (int i = 1; i <= j; i++)
if (isPal[i][j]) dp[j] = min(dp[j], dp[i - 1] + 1);
}
return dp[n - 1];
}

Complexity: O(n^2) time overall (palindrome table O(n^2) + 1-D DP O(n^2)), O(n^2) space.

Common Mistakes & Interview Notes

• This 1-D dp[j] reformulation ('min cuts for prefix ending at j') is faster than the raw (i,j) MCM formulation and is
 what most interviewers expect for LeetCode 132.

4.6 Evaluate Expression to True — Boolean Parenthesization (Recursion)

Problem:
Given a boolean expression with symbols T, F and operators &, |, ^, count the number of ways to parenthesize it so it
evaluates to True.

How to Recognize It
• MCM-style interval DP over the operator positions, but each subrange has TWO answers to track: ways to be
True and ways to be False.

Recurrence Relation
For each operator at position k splitting into left [i,k-1] and right [k+1,j]:
& : True ways += Lt*Rt
| : True ways += Lt*Rt + Lt*Rf + Lf*Rt
^ : True ways += Lt*Rf + Lf*Rt
(False ways = total ways at that split − True ways)

C++17 Solution
// countWays(i, j) returns {waysTrue, waysFalse} for substring i..j (only symbols,
operators are between)
pair<long long,long long> countWaysRec(string& s, int i, int j) {
if (i == j) return { s[i]=='T' ? 1LL : 0LL, s[i]=='F' ? 1LL : 0LL };
long long trueWays = 0, falseWays = 0;
for (int k = i + 1; k < j; k += 2) { // k is always an operator index
auto [lt, lf] = countWaysRec(s, i, k - 1);
auto [rt, rf] = countWaysRec(s, k + 1, j);
long long total = (lt + lf) * (rt + rf);
long long tWays = 0;
if (s[k] == '&') tWays = lt * rt;
else if (s[k] == '|') tWays = lt*rt + lt*rf + lf*rt;
else /* '^' */ tWays = lt*rf + lf*rt;
trueWays += tWays;
falseWays += (total - tWays);
}
return { trueWays, falseWays };
}

Complexity: Exponential without memoization (Catalan-number growth).

Common Mistakes & Interview Notes

• Every symbol is at an even index and every operator at an odd index — the loop step of 2 relies on this.

4.7 Evaluate Expression to True — Memoization Using a 3D Matrix

Problem:
Same problem, memoized with a 3D array dp[i][j][isTrue] (isTrue is 0 or 1).

How to Recognize It
• State (i, j, wantTrue) — memoize both the True-count and False-count table using a fixed-size 3D array since i, j
are bounded by string length.

Recurrence Relation
Same combine rules as 4.6, but each (i,j,0/1) result is cached instead of recomputed.

C++17 Solution
long long dp3[200][200][2]; // dp3[i][j][1]=true ways, dp3[i][j][0]=false ways
bool computed[200][200];
pair<long long,long long> countWaysMemo(string& s, int i, int j) {
if (i == j) return { s[i]=='T'?1LL:0LL, s[i]=='F'?1LL:0LL };
if (computed[i][j]) return { dp3[i][j][1], dp3[i][j][0] };
long long trueWays = 0, falseWays = 0;
for (int k = i + 1; k < j; k += 2) {
auto [lt, lf] = countWaysMemo(s, i, k - 1);
auto [rt, rf] = countWaysMemo(s, k + 1, j);
long long total = (lt + lf) * (rt + rf);
long long tWays = (s[k]=='&') ? lt*rt
: (s[k]=='|') ? lt*rt+lt*rf+lf*rt
: lt*rf+lf*rt;
trueWays += tWays;
falseWays += total - tWays;
}
computed[i][j] = true;
dp3[i][j][1] = trueWays; dp3[i][j][0] = falseWays;
return { trueWays, falseWays };
}

Complexity: O(n^3) time, O(n^2) space (fixed 3D array bounded by max string length).

Common Mistakes & Interview Notes

• A fixed-size global array avoids repeated allocation, which matters for GFG's tight time limits on this problem.

4.8 Evaluate Expression to True — Memoization Using a Map

Problem:
Same problem, memoized using an unordered_map keyed by a string (e.g., "i,j") for cleaner code at the cost of speed.

How to Recognize It
• Same recurrence as 4.6/4.7; only the memo storage mechanism changes.

Recurrence Relation
Identical recurrence to 4.6, cached in memo[to_string(i)+','+to_string(j)].
C++17 Solution
unordered_map<string, pair<long long,long long>> memo;
pair<long long,long long> countWaysMap(string& s, int i, int j) {
if (i == j) return { s[i]=='T'?1LL:0LL, s[i]=='F'?1LL:0LL };
string key = to_string(i) + "," + to_string(j);
if ([Link](key)) return memo[key];
long long trueWays = 0, falseWays = 0;
for (int k = i + 1; k < j; k += 2) {
auto [lt, lf] = countWaysMap(s, i, k - 1);
auto [rt, rf] = countWaysMap(s, k + 1, j);
long long total = (lt + lf) * (rt + rf);
long long tWays = (s[k]=='&') ? lt*rt
: (s[k]=='|') ? lt*rt+lt*rf+lf*rt
: lt*rf+lf*rt;
trueWays += tWays;
falseWays += total - tWays;
}
return memo[key] = { trueWays, falseWays };
}

Complexity: O(n^3) time with extra hashing overhead, O(n^2) space.

Common Mistakes & Interview Notes

• Slower than the 3D array in practice due to string hashing — this lecture exists specifically to show the trade-off
between code simplicity and raw speed; prefer the array version for tight TLE limits.

4.9 Scramble String — Recursion

Problem:
Given two strings s1 and s2 of equal length, determine whether s2 is a scrambled version of s1 (formed by recursively
swapping the two halves of any substring). (LeetCode 87)

How to Recognize It
• MCM-style: try every split point k inside the string; either the halves match without swapping or they match
after swapping.

Recurrence Relation
isScramble(s1,s2) = true if s1==s2
Otherwise: OR over split k of
(isScramble(s1[0..k], s2[0..k]) AND isScramble(s1[k..], s2[k..])) [no swap]
OR (isScramble(s1[0..k], s2[len-k..]) AND isScramble(s1[k..], s2[0..len-k])) [swap]

C++17 Solution
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
if ([Link]() != [Link]()) return false;
string a = s1, b = s2;
sort([Link](), [Link]()); sort([Link](), [Link]());
 if (a != b) return false; // pruning: different character sets

int n = [Link]();
for (int k = 1; k < n; k++) {
// no swap
if (isScramble([Link](0, k), [Link](0, k)) &&
isScramble([Link](k), [Link](k))) return true;
// swap
if (isScramble([Link](0, k), [Link](n - k)) &&
isScramble([Link](k), [Link](0, n - k))) return true;
}
return false;
}

Complexity: Exponential without memoization — extremely slow beyond short strings.

Common Mistakes & Interview Notes

• The character-set pruning check (sorted comparison) is essential — without it, recursion depth explodes even for
the 'false' base cases.

4.10 Scramble String — Memoization

Problem:
Same problem, cached using a map keyed on the pair of substrings to eliminate repeated work.

How to Recognize It
• Overlapping subproblems: identical (s1_substring, s2_substring) pairs recur across different split choices.

Recurrence Relation
Same recurrence as 4.9, cached in unordered_map<string, bool> keyed by s1+"_"+s2.

C++17 Solution
unordered_map<string, bool> scrambleMemo;
bool isScrambleMemo(string s1, string s2) {
if (s1 == s2) return true;
if ([Link]() != [Link]()) return false;
string key = s1 + "_" + s2;
if ([Link](key)) return scrambleMemo[key];

string a = s1, b = s2;

sort([Link](), [Link]()); sort([Link](), [Link]());
if (a != b) return scrambleMemo[key] = false;

int n = [Link]();
for (int k = 1; k < n; k++) {
if (isScrambleMemo([Link](0,k), [Link](0,k)) &&
isScrambleMemo([Link](k), [Link](k)))
return scrambleMemo[key] = true;
if (isScrambleMemo([Link](0,k), [Link](n-k)) &&
 isScrambleMemo([Link](k), [Link](0,n-k)))
return scrambleMemo[key] = true;
}
return scrambleMemo[key] = false;
}

Complexity: O(n^4) time (n^2 distinct substring pairs × O(n) split loop × O(n) substr cost), O(n^2) map entries.

Common Mistakes & Interview Notes

• Using string keys instead of index-based keys is necessary here because both strings can independently shrink
from either end — unlike the fixed-origin (i,j) ranges elsewhere in this chapter.
Chapter 5 — Egg Dropping Puzzle
A distinct DP pattern from a classic puzzle: minimize the worst-case number of trials to find the critical floor, given a
limited number of eggs. Recognize it by: 'minimize the maximum number of attempts', 'eggs may break', 'floors'.

5.1 Egg Dropping — Recursive

Problem:
Given e eggs and f floors, find the minimum number of trials needed in the worst case to determine the critical floor
at which eggs start breaking.

How to Recognize It
• State: (e, f) = number of eggs available and number of floors still to check.
• Choice: drop from floor k (1<=k<=f); if it breaks, recurse with (e-1, k-1); if it survives, recurse with (e, f-k). Take
the worst (max) of these two, then the best (min) over all choices of k.

Recurrence Relation
eggDrop(e,f) = min over k in [1,f] of 1 + max( eggDrop(e-1,k-1), eggDrop(e,f-k) )
Base cases: eggDrop(1,f)=f; eggDrop(e,0)=0; eggDrop(e,1)=1

C++17 Solution
int eggDropRec(int e, int f) {
if (f == 0 || f == 1) return f;
if (e == 1) return f;
int minTrials = INT_MAX;
for (int k = 1; k <= f; k++) {
int broken = eggDropRec(e - 1, k - 1);
int survived = eggDropRec(e, f - k);
minTrials = min(minTrials, 1 + max(broken, survived));
}
return minTrials;
}

Complexity: Exponential — O(f^e) roughly, unusable beyond tiny inputs.

Common Mistakes & Interview Notes

• Interviewers frequently start here specifically to watch you notice how slow the brute force is before asking for
memoization.

5.2 Egg Dropping — Memoization

Problem:
Same problem, cached with a 2D array on (eggs, floors).
How to Recognize It
• Overlapping subproblems: (e, f) pairs repeat heavily across the k-loop of different parent calls.

Recurrence Relation
Same as 5.1, cached in dp[e][f].

C++17 Solution
vector<vector<int>> eggMemo;
int eggDropMemo(int e, int f) {
if (f == 0 || f == 1) return f;
if (e == 1) return f;
if (eggMemo[e][f] != -1) return eggMemo[e][f];
int minTrials = INT_MAX;
for (int k = 1; k <= f; k++) {
int broken = eggDropMemo(e - 1, k - 1);
int survived = eggDropMemo(e, f - k);
minTrials = min(minTrials, 1 + max(broken, survived));
}
return eggMemo[e][f] = minTrials;
}

Complexity: O(e * f^2) time, O(e*f) space.

Common Mistakes & Interview Notes

• Still too slow for large f (e.g., f=10^4) because of the inner O(f) search over k — solved next.

5.3 Egg Dropping — Optimized with Binary Search

Problem:
Same problem, optimized to remove the inner linear search over floor k using binary search.

How to Recognize It
• As k increases, eggDrop(e-1,k-1) increases monotonically and eggDrop(e,f-k) decreases monotonically.
• We are looking for the k where these two curves cross — binary search finds it in O(log f) instead of O(f).

Recurrence Relation
Same recurrence as 5.1/5.2, but the search over k is replaced with binary search on the
monotonic broken/survived curves.

C++17 Solution
vector<vector<int>> eggMemoBS;
int eggDropBinarySearch(int e, int f) {
if (f == 0 || f == 1) return f;
if (e == 1) return f;
 if (eggMemoBS[e][f] != -1) return eggMemoBS[e][f];

int lo = 1, hi = f, ans = INT_MAX;

while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int broken = eggDropBinarySearch(e - 1, mid - 1);
int survived = eggDropBinarySearch(e, f - mid);
int worst = 1 + max(broken, survived);
ans = min(ans, worst);
if (broken > survived) hi = mid - 1; // move toward fewer floors above
else lo = mid + 1; // move toward more floors above
}
return eggMemoBS[e][f] = ans;
}

Complexity: O(e * f * log f) time, O(e*f) space — a large practical improvement, and the version expected for LeetCode
887 (Super Egg Drop) to avoid TLE.

Common Mistakes & Interview Notes

• An even faster O(e log f) formulation exists using a differently-defined DP ('max floors coverable with e eggs and t
trials') — worth mentioning as a follow-up if asked to optimize further.
Chapter 6 — DP on Trees
DP on Trees applies the same memoization idea to tree recursion: each node's answer is computed from its children's
answers, computed once via post-order traversal (no repeated recomputation is possible on a tree, so the 'DP' here is
really about combining subtree results correctly and efficiently, often carrying extra state through recursion).

6.1 Diameter of a Binary Tree

Problem:
Find the length of the longest path between any two nodes in a binary tree (the path may or may not pass through
the root). (LeetCode 543)

How to Recognize It
• For each node, the longest path through it equals height(left subtree) + height(right subtree).
• Naively recomputing height() for every node gives O(n^2); compute height and update the diameter
simultaneously in one post-order pass to get O(n).

Recurrence Relation
height(node) = 1 + max(height([Link]), height([Link]))
diameter = max over all nodes of (height(left) + height(right))

C++17 Solution
int diameterResult = 0;
int height(TreeNode* node) {
if (!node) return 0;
int leftHeight = height(node->left);
int rightHeight = height(node->right);
diameterResult = max(diameterResult, leftHeight + rightHeight);
return 1 + max(leftHeight, rightHeight);
}
int diameterOfBinaryTree(TreeNode* root) {
diameterResult = 0;
height(root);
return diameterResult;
}

Complexity: O(n) time (single post-order traversal), O(h) space for the recursion stack (h = tree height).

Common Mistakes & Interview Notes

• Common mistake: writing a separate height() call inside a separate diameter() recursion — that degrades to
O(n^2) on skewed trees.
6.2 Maximum Path Sum in a Binary Tree
Problem:
Find the maximum sum of any path in a binary tree; a path may start and end at any node (does not need to pass
through the root or include the root at all). (LeetCode 124)

How to Recognize It
• Similar to diameter, but instead of heights we track the maximum single-branch sum a node can contribute
upward, while updating a global best using both branches at once.

Recurrence Relation
maxSingleBranch(node) = [Link] + max(0, maxSingleBranch(left), maxSingleBranch(right))
globalBest = max(globalBest, [Link] + max(0,left) + max(0,right))

C++17 Solution
int globalBest = INT_MIN;
int maxSingleBranch(TreeNode* node) {
if (!node) return 0;
int left = max(0, maxSingleBranch(node->left));
int right = max(0, maxSingleBranch(node->right));
globalBest = max(globalBest, node->val + left + right);
return node->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
globalBest = INT_MIN;
maxSingleBranch(root);
return globalBest;
}

Complexity: O(n) time, O(h) space.

Common Mistakes & Interview Notes

• Clamping negative branch sums to 0 (max(0, ...)) is the key trick — a node should never 'add' a negative
contribution from a child.

6.3 Maximum Path Sum Between Two Leaf Nodes

Problem:
A variant requiring the path to start and end at leaf nodes specifically (not any node).

How to Recognize It
• Same idea as 6.2, but a node can only contribute to the global answer through two children if BOTH children
exist (a true leaf-to-leaf path can't 'turn' at a node with only one child).

Recurrence Relation
If a node has both children: globalBest considers left + [Link] + right.
 If a node has only one child, the path must continue through that one child only (no
turning).

C++17 Solution
int leafBest = INT_MIN;
int maxLeafBranch(TreeNode* node) {
if (!node) return 0;
if (!node->left && !node->right) return node->val; // true leaf

if (!node->left) return node->val + maxLeafBranch(node->right);

if (!node->right) return node->val + maxLeafBranch(node->left);

int left = maxLeafBranch(node->left);

int right = maxLeafBranch(node->right);
leafBest = max(leafBest, left + node->val + right);
return node->val + max(left, right);
}
int maxPathSumLeafToLeaf(TreeNode* root) {
leafBest = INT_MIN;
maxLeafBranch(root);
return leafBest;
}

Complexity: O(n) time, O(h) space.

Common Mistakes & Interview Notes

• Beginner mistake: allowing a single-child node to be treated as a 'leaf' for the purposes of ending a path — the
problem strictly requires a node with zero children.
Final Chapter — DP Pattern Map & Cheat Sheet
1. Complete DP Pattern Map
Pattern Recognize By Example Problems

0/1 Knapsack Choose items once each to hit a Knapsack, Subset Sum, Target Sum
target/capacity

Unbounded Knapsack Items may repeat unlimited times Rod Cutting, Coin Change

LCS / Two-Pointer String DP Compare two sequences with LCS, SCS, Edit Distance, LPS
match/skip choices

MCM / Interval (Partition) DP Choose a split point k inside a range MCM, Palindrome Partitioning,
Boolean Parenthesization, Scramble
String

Egg Drop style DP Minimize worst-case trials under Egg Dropping, Binary Search
constraints optimization

DP on Trees Combine children's post-order Diameter, Max Path Sum

results

2. When to Use Recursion vs Memoization vs Tabulation

• Recursion: use only to derive and validate the recurrence relation; never submit pure recursion for n beyond
~20-25.
• Memoization (top-down): best when not all states are actually visited, or when the state space is irregular (e.g.,
sparse via a map).
• Tabulation (bottom-up): best when all states must be filled anyway, avoids recursion-stack overflow, and is
easier to space-optimize.

3. How to Identify DP in an Interview

• The problem asks for optimal value (min/max), a count of ways, or a yes/no reachability — not the literal
enumeration of all solutions.
• A greedy local choice provably fails on some example you can construct in 30 seconds.
• You can describe the problem using a small number of changing parameters (the state).
• Smaller versions of the exact same problem reappear when you draw the recursion tree.

4. Memoization Template
unordered_map<long long, int> memo; // or vector<vector<int>> for bounded states

int solve(/* params defining state */) {

// 1. base case(s)
if (/* base condition */) return baseValue;
 // 2. check memo
long long key = encodeState(/* params */);
if ([Link](key)) return memo[key];

// 3. recursive relation combining smaller states

int result = /* combine sub-calls */;

// 4. store and return

return memo[key] = result;
}

5. Tabulation Template
vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));

// 1. initialize base cases

for (int j = 0; j <= M; j++) dp[0][j] = /* base value */;
for (int i = 0; i <= N; i++) dp[i][0] = /* base value */;

// 2. fill table in an order where dependencies are already computed

for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
dp[i][j] = /* same relation as recursion, using dp[i-1][..], dp[i][j-1], etc. */;

return dp[N][M];

6. Space Optimization Guide

• If dp[i][*] only depends on dp[i-1][*], keep two 1-D arrays (prev, curr) and swap after each outer iteration.
• If dp[i][*] depends on dp[i][*] itself (Unbounded Knapsack style), a single 1-D array reused in place is enough.
• If you need to reconstruct/print the answer (subsequence, partition, path), you cannot space-optimize — keep
the full table.

7. Complete Complexity Cheat Sheet

Pattern Time Space

0/1 Knapsack O(n*W) O(n*W) → O(W)

Unbounded Knapsack O(n*W) O(n*W) → O(W)

LCS family O(n*m) O(n*m) → O(min(n,m))

MCM / Interval DP O(n^3) O(n^2)

Egg Dropping (binary search) O(e*f*log f) O(e*f)

DP on Trees O(n) O(h) recursion stack

8. Most Common DP Mistakes (Across All Patterns)

• Wrong base case indexing (0-indexed string vs 1-indexed dp table).
 • Iterating the space-optimized 1-D array in the wrong direction (right-to-left needed for 0/1 Knapsack, left-to-
right for Unbounded Knapsack).
• Forgetting to check parity/feasibility conditions before dividing a target sum (e.g., Equal Partition, Target Sum).
• Off-by-one errors in interval DP loops (filling by 'gap length' rather than row/column order).
• Integer overflow when counting large numbers of ways — use long long and take modulo where required.
• Not initializing memo tables to a genuinely unreachable sentinel (-1 for count/length problems only works if -1
can never be a valid answer).

9. Last-Minute Revision Notes

• Knapsack family = include/exclude choice on (index, capacity).
• LCS family = match/skip choice on (i, j) pointers into two sequences.
• MCM family = choose a split point k inside a range (i, j).
• Egg Drop = minimize the worst case over a choice of trial floor, optimized via binary search.
• Tree DP = post-order combine of children's results, computed once per node.

10. One-Page DP Cheat Sheet

Five-Step Method for Any New DP Problem

• Write the brute-force recursion first — identify the choices at each step.
• Identify the state: the minimal parameters that change between calls.
• Add memoization on that state; verify the recursion tree collapses.
• Convert to tabulation by filling the table in dependency order.
• Space-optimize only after correctness is confirmed on the tabulated version.