Knowledge Guide
Home › DSA

Dynamic Programming

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

0 / 80 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.

  1. 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).
  2. Base cases: if n==0 return 0; if n<=2 return 1. Initialize a=0, b=1, c=1.
  3. Transition: for i from 3 to n: next = a+b+c; then slide the window: a=b, b=c, c=next.
  4. 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.
  5. 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?

  1. 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?"
  2. Recurrence: dp[i][s] = dp[i-1][s] (skip nums[i]) OR dp[i-1][s-nums[i]] (take it, when s >= nums[i]).
  3. Base case: dp[0][0]=true (empty subset makes sum 0); dp[0][s>0]=false.
  4. 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.
  5. 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.
  6. 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