DSA in 30 Days, Episode 9: Greedy and Dynamic Programming with Tested Examples
Greedy commits to one choice. Dynamic programming keeps answers to smaller problems. The hard part is knowing which one fits. This is Episode 9 of TechVani's DSA in 30 Days series: learn the rule, test it, and explain why it works. These are general student notes, not an official university syllabus.
Video for this lesson: not uploaded yet. The notes above are the complete tested lesson; the matching video is still being made.
Start with this question: you have several activities but only one room. Should you pick the activity that starts first, ends first, or lasts the shortest time? All sound reasonable. Only one of these rules solves the unweighted activity-selection problem in general.
1. What, why, where and how
| Question | Greedy | Dynamic programming |
|---|---|---|
| What? | Make a locally best choice and continue without revisiting it. | Define smaller states, solve them and reuse their answers. |
| Why? | A proven safe choice can remove the need to search all combinations. | Repeated subproblems waste work; store each useful result. |
| Where? | Unweighted activity selection; fractional knapsack; several graph algorithms. | Minimum coins for arbitrary denominations; 0/1 knapsack; sequence and path problems. |
| How? | Choose a rule, prove it is safe, then implement it. | Define state, transition, base case and computation order. |
2. Greedy: select the most activities
Each activity has a start and a finish time. One room can hold only one activity at a time, and all activities have equal importance. Our intervals are half-open: [start, finish). An activity ending at 3 and another starting at 3 do not overlap. We require start < finish.
| Activity | Start | Finish | Duration |
|---|---|---|---|
| A | 0 | 6 | 6 |
| B | 1 | 3 | 2 |
| C | 3 | 5 | 2 |
| D | 4 | 7 | 3 |
| E | 5 | 8 | 3 |
| F | 8 | 9 | 1 |
Sort by earliest finish time. Pick the first compatible activity; update the last finish time; keep scanning. Sorting by earliest start can let a long activity block several shorter ones. If activities have different rewards and you want the greatest reward rather than the greatest count, this is a different problem. This greedy rule is not enough.
def select_activities(activities):
chosen = []
last_finish = float('-inf')
for name, start, finish in sorted(activities, key=lambda a: a[2]):
if start >= finish:
raise ValueError('Each activity needs start < finish')
if start >= last_finish:
chosen.append(name)
last_finish = finish
return chosenactivities = [('A', 0, 6), ('B', 1, 3), ('C', 3, 5),
('D', 4, 7), ('E', 5, 8), ('F', 8, 9)]
print(select_activities(activities))
# ['B', 'C', 'E', 'F']| Scan order | Check | Decision |
|---|---|---|
| B [1,3) | No previous activity | Pick B; last finish = 3 |
| C [3,5) | 3 >= 3 | Pick C; last finish = 5 |
| A [0,6) | 0 < 5 | Skip A |
| D [4,7) | 4 < 5 | Skip D |
| E [5,8) | 5 >= 5 | Pick E; last finish = 8 |
| F [8,9) | 8 >= 8 | Pick F; last finish = 9 |
Why earliest finish is safe: take any optimal schedule and look at its first activity. Replace that activity with the earliest-finishing one. The replacement ends no later, so all later activities still fit. The schedule keeps the same size. After this choice, apply the same argument to the remaining compatible activities. This is an exchange argument, not a claim that every locally best choice works.
Cost: sorting takes O(n log n); the scan takes O(n). This Python version creates a sorted list and a result list, so it uses O(n) extra space. If the input is already sorted, the selection scan is linear. Ties in finish time do not change the maximum count, though the selected names may differ.
3. A counterexample: greedy coin change
Suppose denominations are 1, 3 and 4. You may use each denomination any number of times. To make 6, a largest-coin-first rule takes 4, then 1, then 1. That is 3 coins. But 3 + 3 uses only 2. The greedy result makes the right amount, yet it does not minimize the number of coins.
def greedy_coins(coins, amount):
used = []
for coin in sorted(set(coins), reverse=True):
while amount >= coin:
amount -= coin
used.append(coin)
return used if amount == 0 else Noneprint(greedy_coins([1, 3, 4], 6))
# [4, 1, 1]4. Dynamic programming: state, transition, base case, order
For minimum coins, let dp[t] mean the fewest coins needed to make total t. That sentence is the state definition. To make t, choose a last coin c and add it to a solution for t - c. Try every usable denomination and keep the smallest count.
dp[0] = 0
dp[t] = min(1 + dp[t - c] for usable coins c)An unreachable total stays at infinity, our marker for "no solution yet". We fill totals from 1 upward because all coin values are positive, so t - c is smaller than t. The smaller answer is already available. With k denominations and target A, this implementation takes O(Ak) time and O(A) space.
def min_coins(coins, amount):
if amount < 0 or any(c <= 0 for c in coins):
raise ValueError('Use a nonnegative amount and positive coins')
dp = [0] + [float('inf')] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total:
dp[total] = min(dp[total], 1 + dp[total - coin])
return None if dp[amount] == float('inf') else dp[amount]print(min_coins([1, 3, 4], 6)) # 2
print(min_coins([2, 4], 3)) # None
print(min_coins([2, 4], 0)) # 0| Total t | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| dp[t] | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
At total 6, taking coin 1 gives 1 + dp[5] = 3; taking coin 3 gives 1 + dp[3] = 2; taking coin 4 gives 1 + dp[2] = 3. The minimum is 2. This function returns the count, not the actual coin list. To return the list, also remember which coin achieved each best answer and walk backward from the target.
5. Memoization versus tabulation
Both reuse smaller answers. Memoization starts from the requested answer, calls smaller problems and caches results. Tabulation starts from base cases and fills answers in a dependency-safe order. Recursion alone is not dynamic programming: it must avoid recomputing useful repeated states.
Fibonacci is a small demonstration. We use F(0) = 0 and F(1) = 1. For n >= 2, F(n) = F(n - 1) + F(n - 2). The same smaller values occur repeatedly in naive recursion.
from functools import lru_cache
def fib_memo(n):
if n < 0:
raise ValueError('n must be nonnegative')
@lru_cache(maxsize=None)
def solve(k):
if k < 2:
return k
return solve(k - 1) + solve(k - 2)
return solve(n)def fib_table(n):
if n < 0:
raise ValueError('n must be nonnegative')
dp = [0] * (n + 1)
if n >= 1:
dp[1] = 1
for k in range(2, n + 1):
dp[k] = dp[k - 1] + dp[k - 2]
return dp[n]print(fib_memo(10)) # 55
print(fib_table(10)) # 55| Point | Memoization | Tabulation |
|---|---|---|
| Direction | Requested state down to base cases | Base cases up to requested state |
| Repeated work | Cache avoids recomputation | Each table state is filled once |
| Memory here | O(n) cache plus O(n) recursion stack | O(n) table, no recursion stack |
| Python limitation | Large n can hit recursion depth | Loop avoids that recursion limit |
The cache in this example is created fresh inside fib_memo, so separate calls do not share old results. The time is O(n) additions in the usual classroom model. Python integers grow as Fibonacci values grow, so very large n also involves larger-number arithmetic. The table can be reduced to two running values if you need only F(n), because the next value needs only its two predecessors.
6. 0/1 knapsack: each item at most once
You have a bag with capacity 5. Each item has a positive integer weight and a nonnegative value. Take a whole item or leave it; you cannot cut it into pieces or use it again. Maximize total value without exceeding capacity. You do not need to fill the bag exactly.
| Item | Weight | Value | Value / weight |
|---|---|---|---|
| A | 2 | 6 | 3 |
| B | 3 | 7 | 7 / 3 |
| C | 4 | 10 | 2.5 |
Highest-value-first takes C and gets value 10. Highest-value-per-weight first takes A; capacity 3 remains, so it can also take B and gets 13. In this example that second rule happens to work. That does not make it safe in general. For items (weight 3, value 5) and (weight 4, value 6) at capacity 4, density-first takes the first item for 5, while the second alone gives 6. Fractional knapsack allows cutting an item and has a different answer and proof.
Let dp[i][c] mean the best value using only the first i items with capacity c. For item i, there are two choices: skip it, or take it if it fits. In both choices, the remaining answer must come from the previous row, because the item is available at most once.
skip = dp[i - 1][c]
take = value + dp[i - 1][c - weight] # only if weight <= c
dp[i][c] = max(skip, take)Base case: with no items, the best value is 0 at every capacity. We also get 0 at capacity 0 because this lesson requires positive weights. Our code returns both the maximum value and its table so you can inspect the trace.
def knapsack(items, capacity):
if capacity < 0 or any(w <= 0 or v < 0 for w, v in items):
raise ValueError('Use positive weights and nonnegative values/capacity')
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i, (weight, value) in enumerate(items, start=1):
for c in range(capacity + 1):
dp[i][c] = dp[i - 1][c] # skip this item
if weight <= c:
dp[i][c] = max(dp[i][c], value + dp[i - 1][c - weight])
return dp[n][capacity], dpvalue, table = knapsack([(2, 6), (3, 7), (4, 10)], 5)
print(value) # 13| Items considered / capacity | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| None | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 6 | 6 | 6 | 6 |
| A, B | 0 | 0 | 6 | 7 | 7 | 13 |
| A, B, C | 0 | 0 | 6 | 7 | 10 | 13 |
The bottom-right cell is 13. At row B, capacity 5, skipping B gives 6; taking B gives 7 + dp[1][2] = 13. At row C, capacity 5, skipping C keeps 13; taking C gives 10 + dp[2][1] = 10. So C is not needed. A and B have total weight 2 + 3 = 5 and total value 6 + 7 = 13.
Cost: O(nW) time and O(nW) space for n items and integer capacity W. This is pseudopolynomial: W is the numeric capacity, not the number of bits used to write it. A huge capacity can make this table impractical even with few items. The full table also helps recover chosen items. If you keep only one row for value computation, iterate capacities downward to avoid using the current item again.
7. How to choose a method
| Ask yourself | What it tells you |
|---|---|
| Can I prove this local choice can be part of an optimal solution? | A greedy solution may fit. Test an exchange or safety argument. |
| Does one choice leave several smaller alternatives to compare? | Try a recurrence; define exactly what each state includes. |
| Do different paths reach the same smaller state? | Caching or tabulation may avoid repeated work. |
| Is the state count small enough? | Estimate memory and time before allocating a table. |
| Does the goal use counts, rewards, exact fill or at-most capacity? | These are different problems; do not reuse a rule blindly. |
Greedy and DP can both rely on optimal substructure: optimal answers contain suitable optimal smaller answers. Greedy needs the extra guarantee that a specific local choice is safe. DP can compare several choices instead. DP is not automatically fast: a poor or enormous state definition can still be expensive.
8. Exam questions, with direct answers
What is the greedy-choice property?
There exists an optimal solution that includes the proposed greedy choice, so making that choice does not lose the optimum.
What are overlapping subproblems?
The same smaller state is reached more than once. Reusing its answer avoids recomputation.
What is optimal substructure?
An optimal answer can be built from optimal answers to the relevant smaller problems.
Why does earliest finish solve activity selection?
It can replace the first activity of an optimal schedule without blocking any later activity. Repeat on the remaining compatible activities.
Why can largest-coin-first fail?
With coins 1, 3, 4 and amount 6 it uses 3 coins, but 3 + 3 uses 2.
Difference between 0/1 and fractional knapsack?
0/1 requires whole items at most once. Fractional allows pieces. A density-based greedy method is safe for fractional knapsack under its usual assumptions, not for general 0/1 knapsack.
Why call O(nW) pseudopolynomial?
It depends on the numeric W. Writing W in binary needs only about log2(W) bits, so this is not a polynomial bound in input bit length.
Is memoization always better than tabulation?
No. It can avoid states that are never needed, but recursion and cache overhead matter. Tabulation gives explicit order and avoids recursion depth problems.
9. Practice first, then check
Q1. Pick compatible activities from X[0,2), Y[1,4), Z[2,3), U[3,5).
Q2. Coins 1, 3, 4; target 8. What does greedy do, and is that answer optimal?
Q3. Coins 2, 4; target 3. What should the function return?
Q4. Items (3,5), (4,6); capacity 4. Compare density-first with the optimum.
Q5. What extra memory does fib_table use? Can you reduce it?
Q6. In a 0/1 one-row knapsack implementation, why visit capacities downward?
Visual notebook: one safe choice, several DP choices
Activity timeline (half-open intervals)
time 0 1 2 3 4 5 6 7 8 9
A [-----------) skip after C
B [---) pick
C [---) pick
D [-----) skip after C
E [-----) pick
F [-) pick
Chosen: B -> C -> E -> F (count 4)
Touching endpoints are compatible.The timeline is a view of the six intervals already listed, not a different dataset. Earliest finish frees the room sooner; it does not maximize duration or reward.
Coin DP: dependencies for total 6
dp[6] = 2
/ | \
coin1 coin3 coin4
| | |
dp[5]=2 dp[3]=1 dp[2]=2
| | |
1+2=3 1+1=2 1+2=3
^
choose minimum
All dependencies have smaller totals.
Fill 0,1,2,3,4,5,6 in this order.Knapsack memory trap: the scan direction changes the problem
Consider one item with weight 2 and value 6 at capacity 4. In a one-row 0/1 update, going downward reads the old row. Going upward can read a value already updated by this same item.
| Scan | Updates from an all-zero row | Result at capacity 4 |
|---|---|---|
| Down: 4, 3, 2 | dp[4]=6 from old dp[2]=0; dp[3]=6; dp[2]=6 | 6: the item is used once |
| Up: 2, 3, 4 | dp[2]=6; dp[3]=6; dp[4]=6+new dp[2]=12 | 12: the same item was reused |
This is why “O(W) memory” needs an update-order explanation, not only a changed array declaration.
Repeat the Proof Lab yourself
Place this checker after the six functions select_activities, greedy_coins, min_coins, fib_memo, fib_table and knapsack above, then run the file with Python 3. The seed makes the small cases repeatable. Independent subset and BFS answers are compared with the lesson functions; this is evidence for implementation behavior, not a proof for all inputs.
# Run after select_activities, min_coins and knapsack from this lesson.
from itertools import combinations
from collections import deque
from random import Random
rng = Random(9)
def exhaustive_activities(items):
best = 0
for mask in range(1 << len(items)):
chosen = sorted([a for i, a in enumerate(items) if mask >> i & 1],
key=lambda a: a[1])
if all(a[2] <= b[1] for a, b in zip(chosen, chosen[1:])):
best = max(best, len(chosen))
return best
def bfs_coins(coins, target):
queue, seen = deque([(0, 0)]), {0}
while queue:
total, count = queue.popleft()
if total == target:
return count
for coin in coins:
nxt = total + coin
if nxt <= target and nxt not in seen:
seen.add(nxt)
queue.append((nxt, count + 1))
return None
def exhaustive_knapsack(items, capacity):
best = 0
for mask in range(1 << len(items)):
picked = [a for i, a in enumerate(items) if mask >> i & 1]
if sum(w for w, v in picked) <= capacity:
best = max(best, sum(v for w, v in picked))
return best
for _ in range(250):
activities = [(str(i), s, s + rng.randrange(1, 5))
for i in range(rng.randrange(0, 8))
for s in [rng.randrange(0, 10)]]
assert len(select_activities(activities)) == exhaustive_activities(activities)
coins = sorted(rng.sample(range(1, 8), rng.randrange(1, 5)))
target = rng.randrange(0, 21)
assert min_coins(coins, target) == bfs_coins(coins, target)
items = [(rng.randrange(1, 6), rng.randrange(0, 11))
for _ in range(rng.randrange(0, 8))]
capacity = rng.randrange(0, 12)
assert knapsack(items, capacity)[0] == exhaustive_knapsack(items, capacity)
print('Activity subset comparisons: 250 passed')
print('Coin BFS comparisons: 250 passed')
print('Knapsack subset comparisons: 250 passed')
a, b = 0, 1
for n in range(101):
assert fib_memo(n) == fib_table(n) == a
a, b = b, a + b
print('Fibonacci comparisons: 101 passed')
print('Counterexample, amount 6:', greedy_coins([1, 3, 4], 6),
'versus DP count', min_coins([1, 3, 4], 6))Executed output:
Activity subset comparisons: 250 passed
Coin BFS comparisons: 250 passed
Knapsack subset comparisons: 250 passed
Fibonacci comparisons: 101 passed
Counterexample, amount 6: [4, 1, 1] versus DP count 2Two last exam checks
Why does coin BFS give a useful independent check? Every edge adds one positive coin. A breadth-first search reaches a total with the fewest edges first, so its distance is the minimum coin count. Restricting totals to the target is safe because positive coins cannot reduce an overshoot.
Why do finite tests not replace the exchange proof? Tests cover the selected inputs. The exchange proof establishes that the earliest-finish replacement preserves feasibility and optimal count for any input satisfying the stated interval assumptions.
10. Proof Lab and next lesson
The examples in this lesson were executed in Python. We compared activity selection against exhaustive subsets, minimum coins against a breadth-first search of reachable totals, and knapsack against exhaustive subsets on 750 seeded small random cases in total. Fibonacci memoization and tabulation also agreed with a separate iterative sequence for n = 0 through 100. These checks support the implementations; they do not replace the greedy correctness proof.
Before your next exam, write a DP state in one sentence, write the base case, and explain why each dependency is ready. For greedy, name the choice and give a reason it is safe. Those habits matter more than memorizing a table shape.
Previous: Episode 8: graphs, BFS, DFS and shortest paths | Next: Episode 10: backtracking and final revision.
Sources for the algorithm ideas: Oakland University greedy notes; OpenDSA 0/1 knapsack; OpenDSA dynamic programming; MIT knapsack notes; Python cache documentation. Examples and traces are TechVani's own.
Comments
Post a Comment