Part 5 of 6. Dynamic Programming — the hardest skill to teach and the most rewarding to master. Every problem follows the full structure: Problem → Decode → Approach Comparison → Dry Run Trace → Annotated C++ Code → Complexity Footer. No shortcuts.
Step 1 — Define the subproblem: What does dp[i]
mean? Define it in one precise English sentence. Never write
code without this.
Step 2 — Write the recurrence: How does dp[i]
depend on smaller subproblems? This is the DP transition.
Step 3 — Base cases: What are the smallest
subproblems you know the answer to?
Step 4 — Order of computation: Which direction
to fill the table? Ensure dependencies are already computed.
Step 5 — Extract answer: Which cell(s) contain
the final answer?
You can climb 1 or 2 steps at a time. How many distinct ways are there to reach the top of n stairs?
Output: 2 (1+1) or (2)
Output: 3 (1+1+1),(1+2),(2+1)
Output: 8
To reach stair n, your last move was either a 1-step from stair n−1, or a 2-step from stair n−2. So the number of ways to reach n is the number of ways to reach n−1 plus the number of ways to reach n−2. That is the Fibonacci recurrence — every step's answer depends only on the previous two.
Recursively compute ways(n-1) + ways(n-2). Exponential — recomputes same subproblems.
Same recursion with memoization array. Each subproblem solved once.
Only need previous two values — no array needed. Roll forward like Fibonacci.
dp[i] = number of distinct ways to reach stair i.
Transition: dp[i] = dp[i-1] + dp[i-2]. Base
cases: dp[1]=1, dp[2]=2. Since each step only needs the last
two values, replace the array with two variables
a and b. At each step compute next
= a + b, then shift: a = b, b = next.
Houses in a row, each with a non-negative amount. Cannot rob two adjacent houses. Find the maximum amount you can rob.
[1,2,3,1]
4
Rob house 1(1)+3(3)=4
[2,7,9,3,1]
12
At house i you have exactly two choices.
Rob it: gain nums[i] but cannot have robbed
i−1, so best you had before is dp[i−2].
Skip it: gain nothing but carry forward the
best up to dp[i−1]. The recurrence is
dp[i] = max(dp[i−1], dp[i−2] + nums[i]). Only
the last two values are ever needed.
Try every subset of non-adjacent houses. Exponential.
prev2 = best up to i−2, prev1 = best up to i−1. At each step: curr = max(prev1, prev2 + nums[i]).
dp[i] = max money robbing from houses 0..i.
Transition:
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Base:
dp[0]=nums[0], dp[1]=max(nums[0],nums[1]). Space-optimise by
keeping only prev2 and prev1.
Same as House Robber, but houses are in a circle — the first and last houses are adjacent. Cannot rob both.
[2,3,2]
3
[1,2,3,1]
4
The first and last house can never both be robbed. So split into two independent linear problems: Case A: rob from house 0 to n−2 (exclude last). Case B: rob from house 1 to n−1 (exclude first). The answer is max(A, B). Each case is exactly Q142.
Exponential — try all valid subsets of a circular arrangement.
Run robLinear(nums[0..n-2]) and robLinear(nums[1..n-1]). Return the max. Each pass is House Robber I.
Write a helper robRange(lo, hi) that applies
Q142's O(1) solution on the subarray. Call it twice with the
two ranges. The trick of fixing two boundary cases is a
general technique for turning circular problems into linear
ones.
Each element nums[i] is the maximum jump length from position i. Starting at index 0, return true if you can reach the last index.
[2,3,1,1,4]
true
[3,2,1,0,4]
false
At each index i, you can jump to at most i + nums[i]. The key question: as you walk from left to right, does the farthest reachable index ever reach n−1? If at any index i your current farthest reach is less than i itself, you're stranded.
dp[i]=true if position i is reachable. For each reachable i, mark all positions i+1..i+nums[i] as reachable.
Walk left to right. Maintain maxReach. At
each i: if i > maxReach → stranded. Else update
maxReach = max(maxReach, i+nums[i]).
One variable: maxReach. Walk i from 0 to n−1.
If i exceeds maxReach, return false — we're stranded.
Otherwise update maxReach = max(maxReach, i + nums[i]). If
we finish the loop, return true.
Same setup as Jump Game I — guaranteed reachable. Return the minimum number of jumps to reach the last index.
[2,3,1,1,4]
2
0→1→4 (jump to index 1 then 4)
[2,3,0,1,4]
2
Think of this as BFS levels. All indices reachable in exactly k jumps form "level k." From each position in level k, we can reach a new range of positions — forming level k+1. We don't need to track individual positions: just track the farthest index reachable at the current level and the farthest reachable at the next level.
For each i, scan all j < i where j is reachable and j+nums[j] ≥ i.
Track curEnd (end of current jump's reach) and farthest. When i hits curEnd, increment jumps and extend window to farthest.
Three variables: jumps (count),
curEnd (boundary of current jump's reach),
farthest (max reachable from anything in
current window). Walk i from 0 to n−2. Always update
farthest. When i == curEnd: we must jump — increment jumps,
set curEnd = farthest. Stop at n−2 because reaching n−1
during a window already counts.
cost[i] = cost to step from stair i. You can start from index 0 or 1. From each stair you can climb 1 or 2 steps. Find the minimum cost to reach the top (past the last index).
[10,15,20]
15
[1,100,1,1,1,100,1,1,100,1]
6
To reach stair i you came from either i−1 or i−2, paying their cost. So dp[i] = cost[i] + min(dp[i−1], dp[i−2]). The "top" is one step past the last index — the answer is min(dp[n−1], dp[n−2]).
dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Keep only last two values.
Set a=cost[0], b=cost[1]. For i from 2 to n−1: curr = cost[i] + min(a, b). Shift: a=b, b=curr. Answer = min(a, b) — the minimum cost to step from either of the last two stairs to the top.
A message encoded as digits: 'A'=1, 'B'=2, ..., 'Z'=26. Count the number of ways to decode a digit string.
"12"
2
"AB"(1,2) or "L"(12)
"226"
3
"06"
0
Like climbing stairs (1 or 2 steps), but with rules: a 1-digit step is valid only if the digit is not '0'. A 2-digit step is valid only if the two-digit number is between 10 and 26. If neither is valid, dp[i]=0 (dead end). If only one is valid, dp[i] inherits from that one. If both valid, dp[i] = dp[i-1] + dp[i-2].
dp[i] = ways to decode s[0..i-1]. One-digit: s[i-1]≠'0' → add dp[i-1]. Two-digit: s[i-2..i-1] in [10,26] → add dp[i-2].
Use two variables: prev2 (dp[i-2]) and prev1 (dp[i-1]). At position i (1-indexed): check if s[i-1] alone is valid (not '0') and add prev1. Check if s[i-2..i-1] as two digits is in [10,26] and add prev2. Base: dp[0]=1 (empty string one way), dp[1]=1 if s[0]≠'0' else 0.
Given coin denominations and a target amount, find the fewest number of coins that sum to the amount. Return -1 if impossible. Unlimited supply of each coin.
[1,5,6,9]
11
2
5+6=11, 2 coins
dp[a] = fewest coins to make amount a. For each amount a, try using each coin c: if a−c is reachable, then dp[a] = min(dp[a], dp[a−c] + 1). The "+1" accounts for the coin c we just used. Base: dp[0]=0 (zero coins to make amount 0). All others start at ∞.
Try all combinations of coins. Exponential, recomputes subproblems.
Build dp[0..amount]. For each amount, try all coins. O(amount × #coins).
Create dp of size amount+1 initialised to ∞ (INT_MAX/2 to avoid overflow). dp[0]=0. For a from 1 to amount: for each coin c: if c ≤ a and dp[a-c]+1 < dp[a], update dp[a]. Answer: dp[amount] == ∞ ? -1 : dp[amount].
Count the number of combinations (not permutations) of coins that sum to the target amount. Unlimited coins of each denomination.
[1,2,5]
5
4
5, 2+2+1, 2+1+1+1, 1+1+1+1+1
The critical insight: if you iterate coins in the outer loop and amounts in the inner loop, each coin is "introduced" one at a time — so {1,2} and {2,1} are only counted once. This is the classic unbounded knapsack counting pattern.
Outer=amounts, inner=coins → {1,2} and {2,1} counted separately. Wrong for combinations.
Outer=coins, inner=amounts → each coin considered once across all amounts. No duplicates.
dp[a] = number of ways to make amount a. Base: dp[0]=1. For each coin c (outer), for each amount a from c to amount (inner): dp[a] += dp[a-c]. After processing coin c, dp[a] only contains ways using coins seen so far — preventing duplicate combinations.
Return the length of the longest strictly increasing subsequence (elements don't need to be adjacent).
[10,9,2,5,3,7,101,18]
4
[2,3,7,101] or [2,5,7,101]
[0,1,0,3,2,3]
4
For each index i, the LIS ending at i can be extended from any index j < i where nums[j] < nums[i]. So dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]. Base: dp[i]=1 (every element forms a length-1 subsequence by itself). Answer = max(dp[i]).
For each i, scan all j < i with nums[j] < nums[i], take max dp[j]+1. Clear and simple.
Maintain a tails array. Binary search for position of each element. Length of tails = LIS length.
Patience Sort: Maintain array
tails where tails[k] = the smallest tail
element of all increasing subsequences of length k+1. For
each num: binary search for the leftmost position in tails
where tails[pos] ≥ num. Replace tails[pos] with num (or
append if past end). The length of tails is the LIS length.
0/1 Knapsack: Each item used at most once.
Inner loop goes RIGHT to LEFT to prevent re-using. Or use 2D
dp[i][w].
Unbounded Knapsack: Each item used unlimited
times. Inner loop goes LEFT to RIGHT.
Bounded Knapsack: Each item has a limited
count. Split or binary grouping.
Partition / Subset Sum: Special case of 0/1 —
can you reach exactly target weight? dp is boolean or count.
n items each with weight w[i] and value v[i]. Knapsack capacity W. Maximise total value without exceeding capacity. Each item can be used at most once.
[2,3,4,5]
[3,4,5,6]
Output: 7
items 0+1 → w=5,v=7
dp[i][w] = max value using items 0..i−1 with capacity w. At item i: skip it → dp[i−1][w]. include it (if w[i] ≤ w) → v[i] + dp[i−1][w−w[i]]. Space-optimise to 1D by iterating capacity RIGHT to LEFT (prevents an item from being used twice).
Table of n×W. Clear to understand. dp[i][w] = max(dp[i-1][w], v[i]+dp[i-1][w-w[i]]).
dp[w] updated right-to-left ensures item i can only be used once per row.
Initialise dp[0..W] = 0. For each item i: loop w from W down to w[i]: dp[w] = max(dp[w], dp[w−w[i]] + v[i]). The right-to-left order means when we compute dp[w], dp[w−w[i]] still reflects the state WITHOUT item i — preventing reuse.
Can you partition an array into two subsets with equal sum? Return true/false.
[1,5,11,5]
true
[1,5,5] and [11]
[1,2,3,5]
false
If total is odd → impossible immediately. If even, the question reduces to: can any subset sum to total/2? This is the 0/1 Knapsack boolean variant: dp[s] = true if some subset of seen items sums exactly to s. Same right-to-left iteration as Q151.
dp is boolean. dp[0]=true. For each num: loop s from target down to num. dp[s] |= dp[s-num].
target = sum/2. dp[0..target] boolean, dp[0]=true. For each num (right-to-left): dp[s] |= dp[s−num]. If dp[target] becomes true at any point, return early. After all nums: return dp[target].
Assign + or − to each number. Count ways to make the total equal to target.
[1,1,1,1,1]
3
5
-1+1+1+1+1=3
Let P = sum of positive-assigned numbers. Let N = sum of negative-assigned. Then P + N = total, P − N = target. Solving: P = (total + target) / 2. So the question becomes: how many subsets sum to (total+target)/2? This is the counting variant of subset sum — 0/1 knapsack where dp[s] = number of ways.
If (total+target) is odd or target > total → 0 ways. Otherwise target_sum = (total+target)/2. dp[0..target_sum] counting, dp[0]=1. For each num (right-to-left): dp[s] += dp[s−num]. Return dp[target_sum].
Smash stones together. When two stones collide, the difference remains. Minimise the smallest possible remaining weight. (Each stone gets a + or − sign; minimise |sum|.)
[2,7,4,1,8,1]
1
Assign + to some stones (set P) and − to others (set N). Result = |P−N| = |total−2P|. To minimise this, maximise P subject to P ≤ total/2. This is a 0/1 knapsack maximisation where capacity = total/2.
target = total/2. dp[s] = max achievable sum using subset ≤ s. Same as Q151 but maximising. dp[0]=0. For each stone (right-to-left): dp[s] = max(dp[s], dp[s−stone]+stone). Answer = total − 2×dp[target].
Given a string s and a dictionary of words, can s be segmented into a space-separated sequence of dictionary words?
"leetcode"
["leet","code"]
true
"applepenapple"
["apple","pen"]
true
dp[i] = true if the first i characters of s can be broken into dictionary words. Transition: dp[i] is true if there exists some j < i such that dp[j] is true AND s[j..i-1] is in the dictionary. Base: dp[0]=true (empty string is trivially segmented).
Exponential without memo. For each position try all word lengths.
For each i, check all j where dp[j]=true and s[j..i-1] is in word set. Hash set for O(1) lookup.
For i from 1 to n: for j from 0 to i−1: if dp[j] AND s.substr(j, i−j) in wordSet → dp[i]=true, break. Use unordered_set for O(1) lookups. The inner loop is O(n) per position, so total O(n²) plus O(L) per substr check where L=word length.
Count the number of possible ordered sequences (permutations) of numbers from the array that sum to target. Order matters: (1,2) and (2,1) are different.
[1,2,3]
4
7
(1,1,1,1),(1,1,2),(1,2,1)
(2,1,1),(2,2),(1,3),(3,1)
Contrast with Q149 (combinations, coins outer). For permutations, iterate amounts in outer loop, nums in inner loop. At each amount a, for each num: dp[a] += dp[a−num]. This counts ordered sequences because for each total we consider all possible last elements.
dp[a] = ways to make amount a with order. For each a: for each num c: dp[a]+=dp[a-c].
dp[0]=1 (empty sequence). For a from 1 to target: for each num c: if c ≤ a, dp[a] += dp[a−c]. dp[a−c] counts sequences reaching (a−c); adding c as last element gives sequences reaching a. Since we're iterating all c at each a, we naturally count all orderings.
Array of binary strings. Find the largest subset where the total number of 0s ≤ m and total 1s ≤ n.
["10","0001","111001","1","0"]
Output: 4
["10","0001","1","0"] → 5 zeros, 3 ones ✓
Each string is an item with two weights: (count of 0s, count of 1s). The knapsack has two capacities: m (max zeros) and n (max ones). dp[i][j] = max strings selected using at most i zeros and j ones. Same right-to-left update logic as 0/1 knapsack, but in 2D.
For each string with z zeros and o ones: iterate i from m down to z, j from n down to o: dp[i][j] = max(dp[i][j], dp[i−z][j−o] + 1). The double reverse ensures each string is used at most once.
Jobs with start, end, profit. Non-overlapping jobs only. Maximise total profit.
[1,2,3,3]
[3,4,5,6]
[50,10,40,70]
120
Job 0(50)+Job 3(70)
Sort jobs by end time. dp[i] = max profit considering jobs 0..i−1. For job i: skip → dp[i]. Take → profit[i] + dp[j] where j is the index of the last job whose end time ≤ start[i]. Find j with binary search on end times. Transition: dp[i+1] = max(dp[i], profit[i] + dp[j]).
For each job, scan backwards to find last non-overlapping job. O(n) per job.
Sort by end. For each job, binary search for last end ≤ start. O(log n) per job.
Sort jobs by end time. Build dp[0..n] where dp[i] = max profit from first i jobs. For job i (0-indexed): find the rightmost job j where end[j] ≤ start[i] using upper_bound on the sorted end array. dp[i+1] = max(dp[i], profit[i] + dp[j+1]).
Most string DP problems define dp[i][j] as the answer for s1[0..i−1] and s2[0..j−1]. The recurrence branches on whether s1[i−1] == s2[j−1]: if equal, often dp[i-1][j-1]+1. If not, take the best of deleting from either string. Spend time understanding the 2D table — draw it out before coding.
Find the length of the longest common subsequence of two strings. A subsequence doesn't need to be contiguous.
"abcde"
"ace"
3
"ace"
"abc"
"def"
0
dp[i][j] = LCS length of s1[0..i−1] and s2[0..j−1]. If s1[i−1] == s2[j−1]: match! dp[i][j] = dp[i−1][j−1] + 1. If not: the LCS must skip s1[i−1] or s2[j−1] — take the better option: dp[i][j] = max(dp[i−1][j], dp[i][j−1]).
Try all pairs of subsequences. Exponential.
Build table row by row. dp[i][j] from three neighbours. O(m×n) time and space.
Base: dp[0][j]=dp[i][0]=0. For each (i,j): if s1[i−1]==s2[j−1] → dp[i][j]=dp[i−1][j−1]+1. Else → dp[i][j]=max(dp[i−1][j], dp[i][j−1]). Space can be reduced to O(n) using two rolling rows since each row only depends on the row above.
Convert word1 to word2 using minimum operations. Each operation is one of: insert a character, delete a character, or replace a character.
"horse"
"ros"
3
horse→rorse(repl) →rose(del)→ros(del)
Three operations map to three table neighbours: Insert into w1 = dp[i][j−1]+1 (we handled w2[j−1] by inserting). Delete from w1 = dp[i−1][j]+1. Replace = dp[i−1][j−1]+1. If w1[i−1]==w2[j−1]: no operation needed → dp[i−1][j−1]+0. Take the minimum of all valid options.
dp[i][j]=min edit distance for prefixes i,j. Three neighbours + optional free match.
Base: dp[i][0]=i (delete i chars from w1). dp[0][j]=j (insert j chars). For each (i,j): if w1[i−1]==w2[j−1] → dp[i][j]=dp[i−1][j−1] (free). Else → min(dp[i−1][j−1]+1, dp[i−1][j]+1, dp[i][j−1]+1) = min(replace, delete, insert).
Find the length of the longest palindromic subsequence in a string.
"bbbab"
4
"bbbb"
"cbbd"
2
A palindrome reads the same forwards and backwards. Any palindromic subsequence of s must also appear as a subsequence of reverse(s). Therefore LPS(s) = LCS(s, reverse(s)). This reduces to Q159 directly.
Reverse s, compute LCS. Clean two-line solution. O(n²) time and space.
dp[i][j]=LPS of s[i..j]. If s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2. Else max of two shrinks.
dp[i][j] = length of LPS in s[i..j]. Base: dp[i][i]=1. For length l from 2 to n: for each starting i, j=i+l−1: if s[i]==s[j] → dp[i][j]=dp[i+1][j−1]+2. Else → dp[i][j]=max(dp[i+1][j], dp[i][j−1]).
Count the number of distinct subsequences of s which equal t.
"rabbbit"
"rabbit"
3
3 ways to pick one 'b' from the three 'b's
At each pair (i,j): if s[i−1]==t[j−1], we can either use s[i−1] to match t[j−1] (dp[i−1][j−1] ways) or skip s[i−1] (dp[i−1][j] ways). If s[i−1]≠t[j−1], we must skip s[i−1] → dp[i][j]=dp[i−1][j].
Base: dp[i][0]=1 for all i (t="" is always a subsequence). dp[0][j]=0 for j>0. Transition: if s[i−1]==t[j−1]: dp[i][j]=dp[i−1][j−1]+dp[i−1][j]. Else: dp[i][j]=dp[i−1][j].
m×n grid. Start at top-left, reach bottom-right. Can only move right or down. Count distinct paths.
Output: 28
Output: 3
R↓↓, ↓R↓, ↓↓R
dp[i][j] = number of ways to reach cell (i,j). You can only arrive from above (i−1,j) or from the left (i,j−1). So dp[i][j]=dp[i−1][j]+dp[i][j−1]. All top-row and left-column cells = 1 (only one way to reach them — stay on the edge).
Grid approach: dp[i][j]=dp[i-1][j]+dp[i][j-1]. Space-optimise to 1D by noting dp[j] += dp[j-1] in each row (left column stays 1). Math formula: C(m+n-2, m-1) — total moves is m+n-2, choose which m-1 are downward.
Same as Q163 but some cells have obstacles (1=obstacle, 0=free). Count paths that avoid obstacles.
[[0,0,0], [0,1,0], [0,0,0]]
2
Exactly Q163 but with an added rule: if grid[i][j]==1 (obstacle), then dp[i][j]=0. The contribution from an obstacle is blocked — no path passes through it. Build the table identically otherwise.
Initialise the first row: set dp[j]=1 until we hit an obstacle, then all subsequent cells in that row = 0 (can't pass the obstacle). Similarly for the first column. For interior cells: if obstacle → dp[i][j]=0. Else dp[i][j]=dp[i-1][j]+dp[i][j-1].
m×n grid of non-negative integers. Find the path from top-left to bottom-right (right/down only) with minimum sum.
[[1,3,1], [1,5,1], [4,2,1]]
7
1→3→1→1→1=7
To reach (i,j) you came from (i−1,j) or (i,j−1). Add the cost of the current cell to the cheaper of the two. dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]).
Modify grid in-place or use a 1D dp. For the first row: accumulate left to right. For the first column: accumulate top to bottom. For interior: dp[j] = grid[i][j] + min(dp[j], dp[j−1]) where dp[j] is "from above" and dp[j−1] is "from left."
Knight must reach bottom-right from top-left. Cells have positive (health gain) or negative (health loss) values. Health must always stay ≥ 1. Find the minimum initial health needed.
[[-2,-3,3], [-5,-10,1], [10,30,-5]]
7
Going forward is hard because health depends on future cells. Backwards is clean: dp[i][j] = minimum health needed when entering (i,j) to survive the rest of the journey. dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) − dungeon[i][j]). The max(1,…) ensures health never goes below 1.
Fill dp from bottom-right to top-left. Base: dp[m-1][n-1] = max(1, 1 − dungeon[m-1][n-1]). For bottom row (only right neighbour) and right column (only bottom neighbour): fill accordingly. For interior: take min of right and bottom dp values, subtract current cell, max with 1.
Find the largest square containing only 1s in a binary matrix. Return its area.
[["1","0","1","0","0"], ["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
4
If matrix[i][j]=='1': dp[i][j] = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]). The minimum of the three neighbours determines the largest square that can be extended here. If any neighbour is small (has a 0 nearby), the square is constrained. If matrix[i][j]=='0': dp[i][j]=0.
dp[i-1][j] = largest square ending at the cell above. dp[i][j-1] = largest ending at the cell to the left. dp[i-1][j-1] = largest ending diagonally. The new square of side k requires all three to have side ≥ k−1. So the bottleneck is the minimum. Max side seen = answer; area = side².
Interval DP solves problems on contiguous segments. dp[i][j] = answer for segment [i..j]. Fill by increasing length: length 1 first (base), then 2, 3, ... n. For each length, iterate all starting positions i. Compute dp[i][j] by trying every split point k in [i..j] and combining dp[i][k] and dp[k+1][j]. Classic problems: matrix chain multiplication, burst balloons, stone merging.
n balloons with values. Bursting balloon i gives coins nums[i−1]×nums[i]×nums[i+1]. Maximise total coins. Add boundary balloons of value 1 at both ends.
[3,1,5,8]
167
3→1→5→8 gives 167
Thinking about which balloon to burst first is hard because it changes the neighbours. Instead, think about which is burst last. When k is the last balloon in [i..j], its left and right neighbours are the fixed boundaries i−1 and j+1. dp[i][j] = max over all k in [i..j] of: dp[i][k−1] + nums[i−1]×nums[k]×nums[j+1] + dp[k+1][j].
Try every permutation of burst order. Factorial time.
dp[i][j] = max coins from bursting all in [i..j]. Fill by length. Try every last-burst k.
Pad nums with 1 at both ends: nums = [1, ...original..., 1]. dp[i][j] = max coins from bursting balloons i..j (where left boundary is i−1 and right boundary is j+1 in the padded array). Fill by length. For each length l, each start i, j=i+l−1: try each k as last burst: dp[i][j] = max over k of dp[i][k−1] + padded[i−1]×padded[k]×padded[j+1] + dp[k+1][j].
A printer prints consecutive same characters in one turn. Find the minimum turns to print string s.
"aaabbb"
2
"aba"
2
Two cases at (i,j). If s[i]==s[j]: printing them as one run means dp[i][j]=dp[i][j−1] (the last character extends the first's run for free, no extra turn needed — we merge them). Otherwise try every split k: dp[i][j] = min over k of dp[i][k]+dp[k+1][j].
Base: dp[i][i]=1. Fill by length. For each (i,j): start with dp[i][j]=dp[i][j−1]+1 (worst case: print s[j] separately). Then if s[k]==s[j] for any k in [i..j−1]: dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j−1]) because s[j] can be printed with s[k] in the same turn.
Can buy/sell stocks any number of times, but after selling you must wait one day (cooldown). Maximise profit.
[1,2,3,0,2]
3
buy day0,sell day1 cooldown day2,buy day3 sell
day4 → 3
Model as a state machine. held = max
profit while holding a stock. sold = max
profit on the day you just sold. rest =
max profit while not holding and not in cooldown.
Transitions: held' = max(held, rest − price) (buy or
keep). sold' = held + price (sell today). rest' =
max(rest, sold) (cool down or keep resting).
held, sold, rest updated each day. O(1) per day.
Init: held=−∞, sold=0, rest=0. For each price p: held' = max(held, rest−p). sold' = held+p. rest' = max(rest, sold). Update all three simultaneously (use temp variables). Answer = max(sold, rest).
Buy/sell any number of times but pay a fee on each sell. Maximise profit.
[1,3,2,8,4,9]
Output: 8
Simpler than Q170 — no cooldown. held' = max(held, free−price). free' = max(free, held+price−fee). The fee is deducted at sell time.
held = max profit while holding. free = max profit while not holding. Init held=−∞, free=0. Each day: held' = max(held, free−p). free' = max(free, held+p−fee). Answer = free.
Stone Game I: Two players alternate.
Alex picks from either end. Piles have distinct
totals. Does Alex (first player) always win? (Answer:
always true for even n — show the proof.)
Stone Game II: Can take 1..2M piles
from front. M updates each turn. Find max stones Alice
can get.
[5,3,4,5]
true
[2,7,9,4,4]
10
For even-length arrays, the first player can always guarantee winning. Partition into "even-indexed" and "odd-indexed" groups. Since totals differ, one group has more. The first player precommits to always taking from the group with more (can always do so since both endpoints can't be the same parity). This is O(1) — just return true.
Game II Decode — dp[i][M] = Max Stones Alice Can Get From Piles[i..n−1] Given Current M. Let suffix[i] = sum of piles[i..n-1]. dp[i][M] = suffix[i] - dp[i][?] (Alice takes as many as she can, Bob gets the rest). For each take of X (1..2M): dp[i][M] = max over X of (suffix[i] - dp[i+X][max(M,X)]).
Precompute suffix sums. dp[i][m] = max stones current player gets from piles[i..n-1] with current M=m. dp[i][m] = max over x=1..2m of (suffix[i] - dp[i+x][max(m,x)]). Because if current player takes best, opponent gets the rest from what remains. Fill backwards i from n-1 to 0.
Given a list of strings (all same length) and a target string, count the ways to form target by picking one character per column (left to right, reusing columns not allowed after picking from column j).
["acca","bbbb","caca"]
"aba"
6
Pre-count freq[j][c] = how many words have character c at column j. Transition: skip column j → dp[i][j+1]+=dp[i][j]. Use column j → dp[i+1][j+1]+=dp[i][j]×freq[j][target[i]].
Precompute freq[j][c] for each column j and character c. dp[i][j] = ways to form first i chars of target using first j columns. For each column j: can skip (dp[i][j+1]+=dp[i][j]) or use for target[i] if freq[j][target[i]]>0 (dp[i+1][j+1]+=dp[i][j]×freq[j][target[i]]).
Implement regex matching with '.' (matches any char) and '*' (matches zero or more of preceding element).
p="a*" → true
p=".*" → true
p="c*a*b" → true
Three cases at (i,j): 1. p[j−1]='*': either zero uses (dp[i][j−2]) or one-or-more uses (s[i−1] matches p[j−2] AND dp[i−1][j]). 2. p[j−1]='.' or p[j−1]==s[i−1]: dp[i][j]=dp[i−1][j−1] (characters match). 3. Otherwise: false.
Base: dp[0][0]=true. dp[0][j]: only true if p has pattern like "a*b*c*" (star pairs). For each (i,j): handle '*' first (it looks two steps back at j−2). Otherwise check single character match: '.' or exact character.
Given stone piles and integer k, merge k consecutive piles into one pile repeatedly. Each merge costs the sum of the merged piles. Return minimum cost to merge all into one pile, or -1 if impossible.
[3,2,4,1]
2
20
[3,2,4,1]
3
-1
Only segments where (j-i)%(k-1)==0 can collapse to one pile. For each interval, try every split point at intervals of k-1 to maintain valid merge states. Add range sum when the segment becomes mergeable into one.
Try every sequence of merges (factorial). Too slow.
Use prefix sum and interval dp with step (k-1) splitting.
Prepare prefix sums. dp[i][j] = minimum cost to partially merge [i..j]. Iterate len=2..n. For each (i,j) choose mid = i..j-1 with step k-1: dp[i][j]=min(dp[i][j], dp[i][mid]+dp[mid+1][j]). If (j-i)%(k-1)==0, dp[i][j]+=sum(i..j) because one final merge happens.