Dynamic Programming

Step 20 in the DSA path · 37 concepts · 42 problems

0 / 79 complete

📘 Learn Dynamic Programming from zero

Dynamic Programming solves a problem by breaking it into overlapping subproblems and storing each subproblem's answer once in a table, so it is never recomputed. The trigger to reach for DP: you are asked for an optimum (max/min/count/feasibility) over a sequence of choices, where each choice's best result depends on the best results of smaller versions of the same problem (optimal substructure). Classic tell: a brute-force recursion would re-evaluate the same (index, remaining_capacity) state many times. We trace the canonical 0/1 Knapsack: items with weights wt=[1,3,4,5] and values val=[1,4,5,7], capacity W=7. Each item is taken at most once; we want the max total value that fits.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Define the state & table

items: i=1 (w=1,v=1)
       i=2 (w=3,v=4)
       i=3 (w=4,v=5)
       i=4 (w=5,v=7)
capacity W = 7

dp[i][c] = best value using first i items
           within capacity c

     c:  0   1   2   3   4   5   6   7
   i=0 [  0   0   0   0   0   0   0   0 ]   <- base row
   i=1 [  .   .   .   .   .   .   .   . ]
   i=2 [  .   .   .   .   .   .   .   . ]
   i=3 [  .   .   .   .   .   .   .   . ]
   i=4 [  .   .   .   .   .   .   .   . ]

We pick the state dp[i][c] = the maximum value achievable using only the first i items with a capacity budget of c. Row i=0 is the base case: with zero items, every capacity yields value 0. This is safe because it bottoms out the recursion with a known, trivially-correct answer.

Step 2 — Transition (the recurrence)

For each cell, item i has weight wt[i], value val[i]:

  if wt[i] > c:          // item too heavy to fit
      dp[i][c] = dp[i-1][c]            (SKIP only)

  else:                  // we may take it or skip it
      dp[i][c] = max(
          dp[i-1][c],                 (SKIP item i)
          val[i] + dp[i-1][c - wt[i]]  (TAKE item i)
      )

Key: TAKE looks at row i-1 (each item used once).

Each cell makes one binary choice — take item i or skip it — and reuses already-solved smaller states. Looking back at row i-1 (not row i) guarantees each item is counted at most once, which is the defining 0/1 constraint.

Step 3 — Fill row i=1 (item w=1, v=1)

     c:  0   1   2   3   4   5   6   7
   i=0 [  0   0   0   0   0   0   0   0 ]
   i=1 [  0   1   1   1   1   1   1   1 ]  <-- filled
              ^ c=1: wt=1 fits
                TAKE = 1 + dp[0][0]=1
                SKIP = dp[0][1]=0  -> max=1

   c=0: wt=1 > 0  -> SKIP only -> dp[0][0]=0

With only item 1 (weight 1, value 1), any capacity ≥ 1 can hold it once for value 1; capacity 0 holds nothing, so stays 0. Every TAKE references the trusted base row i=0, so the values are provably correct.

Step 4 — Fill row i=2 (item w=3, v=4)

     c:  0   1   2   3   4   5   6   7
   i=0 [  0   0   0   0   0   0   0   0 ]
   i=1 [  0   1   1   1   1   1   1   1 ]
   i=2 [  0   1   1   4   5   5   5   5 ]  <-- filled
                        ^ c=3:
            TAKE = 4 + dp[1][3-3]=dp[1][0]=0 -> 4
            SKIP = dp[1][3]=1            -> max=4
                            ^ c=4:
            TAKE = 4 + dp[1][4-3]=dp[1][1]=1 -> 5
            SKIP = dp[1][4]=1            -> max=5

For c<3 item 2 cannot fit, so we copy the row above. At c=3 taking it (value 4) beats keeping item 1 (value 1); at c=4 we take item 2 and still have room for item 1 (4+1=5). Each decision only reads the finished row above, so no subproblem is recomputed.

Step 5 — Fill row i=3 (item w=4, v=5)

     c:  0   1   2   3   4   5   6   7
   i=0 [  0   0   0   0   0   0   0   0 ]
   i=1 [  0   1   1   1   1   1   1   1 ]
   i=2 [  0   1   1   4   5   5   5   5 ]
   i=3 [  0   1   1   4   5   6   6   9 ]  <-- filled
                                ^ c=5:
          TAKE = 5 + dp[2][5-4]=dp[2][1]=1 -> 6
          SKIP = dp[2][5]=5            -> max=6
                                        ^ c=7:
          TAKE = 5 + dp[2][7-4]=dp[2][3]=4 -> 9
          SKIP = dp[2][7]=5            -> max=9

At c=7, taking item 3 (value 5) leaves capacity 3, whose best (item 2, value 4) is already stored in dp[2][3]=4, giving 5+4=9. We trust that cached optimum instead of re-solving it — that reuse is the whole point of DP.

Step 6 — Fill row i=4 (item w=5, v=7) & read answer

     c:  0   1   2   3   4   5   6   7
   i=0 [  0   0   0   0   0   0   0   0 ]
   i=1 [  0   1   1   1   1   1   1   1 ]
   i=2 [  0   1   1   4   5   5   5   5 ]
   i=3 [  0   1   1   4   5   6   6   9 ]
   i=4 [  0   1   1   4   5   7   8   9 ]  <-- final
                                        ^^^
  c=7: TAKE = 7 + dp[3][7-5]=dp[3][2]=1 -> 8
       SKIP = dp[3][7]=9             -> max=9  ANSWER

At the goal cell dp[4][7], taking item 4 (7 + best-of-capacity-2 = 7+1 = 8) is worse than skipping it to keep the value-9 combo from row 3. The bottom-right cell dp[4][7]=9 is the final answer: max value for capacity 7.

Step 7 — Backtrack to recover chosen items

Walk from dp[4][7] upward; item taken iff value
changed from the row above:

 dp[4][7]=9 == dp[3][7]=9  -> item4 SKIPPED, stay c=7
 dp[3][7]=9 != dp[2][7]=5  -> item3 TAKEN,   c=7-4=3
 dp[2][3]=4 != dp[1][3]=1  -> item2 TAKEN,   c=3-3=0
 dp[1][0]=0 == dp[0][0]=0  -> item1 SKIPPED

Chosen: item2 (w3,v4) + item3 (w4,v5)
Weight = 3+4 = 7  <= 7  OK
Value  = 4+5 = 9  == dp[4][7]  OK

By comparing each cell to the one above, a difference means that item was taken. We recover items 2 and 3, using weight exactly 7 for value 9 — matching the table. This confirms the trace is concrete and self-consistent; time and space are O(n·W).

🎯 Guided practice

Practice 1 (easy) — N-th Tribonacci, space-optimized. Goal: return T(n) in O(1) space.

Define state: we only need the three most recent terms. Call them a, b, c for T(i-3), T(i-2), T(i-1).
Base cases: if n==0 return 0; if n<=2 return 1. Initialize a=0, b=1, c=1.
Transition: for i from 3 to n: next = a+b+c; then slide the window: a=b, b=c, c=next.
Answer: after the loop, c holds T(n). Trace n=4: start (0,1,1) → i=3 next=2 → (1,1,2) → i=4 next=4 → (1,2,4), return 4. Correct.
Pattern learned: when a recurrence looks back a fixed k steps, you don't need the full table — a rolling window of k variables suffices.

Practice 2 (medium) — Subset Sum (the core of the 0/1 Knapsack family). Given positive integers nums and a target, can any subset sum exactly to target?

Spot the pattern: each number is a take-or-skip decision under a sum constraint → 0/1 Knapsack. State = (i, s): "using the first i numbers, can we make sum s?"
Recurrence: dp[i][s] = dp[i-1][s] (skip nums[i]) OR dp[i-1][s-nums[i]] (take it, when s >= nums[i]).
Base case: dp[0][0]=true (empty subset makes sum 0); dp[0][s>0]=false.
1D optimization: collapse to a boolean array dp[0..target] with dp[0]=true. For each num, loop s from target down to num: dp[s] = dp[s] or dp[s-num]. Descending order is critical — it guarantees each item is used at most once; ascending order would let one item be reused, turning this into unbounded knapsack.
Trace nums=[3,4], target=7: start dp=[T,F,F,F,F,F,F,F]. After 3: dp[3]=T → [T,F,F,T,F,F,F,F]. After 4 (s from 7 down to 4): dp[7]=dp[7] or dp[3]=T, dp[4]=dp[4] or dp[0]=T → [T,F,F,T,T,F,F,T]. dp[7]=true → yes.
Why this generalizes: Equal Subset Sum Partition is Subset Sum with target = totalSum/2 (return false immediately if totalSum is odd); Count of Subset Sum swaps the boolean OR for integer addition (dp[s] += dp[s-num]); Target Sum maps the +/- assignment to a subset summing to (totalSum + target)/2, counting those subsets (no solution if that value is non-integer or negative); Minimum Subset Sum Difference finds the largest reachable sum ≤ totalSum/2 and returns totalSum − 2·best. Master this one recurrence and five "different" problems collapse into one. Complexity: O(n·target) time, O(target) space.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard

What two properties must a problem have for Dynamic Programming to apply, and what does each mean?

tap to reveal →

Overlapping subproblems (solving it involves solving the same smaller subproblem multiple times) and optimal substructure (the overall optimal solution can be built from the optimal solutions of its subproblems). Fibonacci has both: fib(4) re-evaluates fib(2) twice and fib(1) thrice, and Fib(n)=Fib(n-1)+Fib(n-2).

💡 OSOS: Overlapping Subproblems + Optimal Substructure.

Flashcard

What is the trigger signal that you should reach for DP on a problem?

tap to reveal →

You are asked for an optimum (max/min/count/feasibility) over a sequence of choices, where each choice's best result depends on the best results of smaller versions of the same problem. The classic tell is a brute-force recursion that re-evaluates the same (index, remaining_capacity) state many times.

💡 Optimum over choices + repeated states = DP.

Flashcard

What is the difference between top-down memoization and bottom-up tabulation?

tap to reveal →

Top-down memoization solves the big problem by recursing into subproblems and caching each result so it isn't recomputed. Bottom-up tabulation avoids recursion, solving all smaller subproblems first by filling an n-dimensional table, then reading the answer at the top. The course advises always starting from a brute-force recursion, then adding memoization and tabulation.

💡 Memo = recurse + cache (top-down); Tabulate = fill table (bottom-up).

Flashcard

In the 0/1 Knapsack DP, what is the state and the transition, and why must TAKE look at row i-1?

tap to reveal →

State dp[i][c] = max value using the first i items within capacity c. Transition: if wt[i]>c then dp[i][c]=dp[i-1][c] (skip); else dp[i][c]=max(dp[i-1][c], val[i]+dp[i-1][c-wt[i]]). TAKE reads row i-1 (not row i) so each item is counted at most once — the defining 0/1 constraint. Complexity is O(n*W).

💡 0/1 = look back one ROW so each item used once.

Flashcard

What single change turns 0/1 Knapsack into Unbounded Knapsack, and what is an example optimum?

tap to reveal →

Unbounded Knapsack allows an unlimited quantity of each item (each item selectable multiple times), whereas 0/1 takes each item at most once. For weights {1,2,3} (apple/orange/melon), profits {15,20,50}, capacity 5, the best is 2 apples + 1 melon = 80 profit.

💡 Unbounded = infinite supply; 2 apples + 1 melon = 80.

Flashcard

For Longest Common Subsequence and Edit Distance, what is the shared state and how do their recurrences differ?

tap to reveal →

Both use state on the two string indexes (i1,i2). LCS: if s1[i]==s2[j], dp=1+dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1]). Edit Distance: on match recurse on (i+1,j+1) with no cost; on mismatch, dp=1+min of delete (i+1,j), insert (i,j+1), replace (i+1,j+1). Both go from exponential brute force to O(m*n) with memoization.

💡 Match: take the diagonal. Mismatch — LCS maxes 2 skips, Edit mins 3 edits.

Q1. Which pair of properties indicates a problem is solvable with Dynamic Programming?

Q2. In the canonical 0/1 Knapsack trace (wt=[1,3,4,5], val=[1,4,5,7], W=7), what is the maximum achievable value at dp[4][7]?

Q3. What distinguishes the 0/1 Knapsack recurrence from the Unbounded Knapsack recurrence?

Q4. For Longest Common Subsequence with state dp[i][j], what is the correct transition when s1[i] does NOT equal s2[j]?

Q5. In Edit Distance, on a character mismatch the recurrence takes 1 + the minimum over which three operations?