Compare a choice rule with a decomposition strategy
A greedy method commits to a locally attractive choice and normally does not undo it. Dynamic programming stores solutions to state-defined subproblems and combines them. The difference is not that greedy methods are careless while DP is automatically correct. Both require a correctness argument matched to the objective and constraints. A greedy approach needs a reason that its local choice can belong to an optimal solution, such as an exchange argument. DP likewise fails if the state omits information or the transitions do not describe the real choices. Identify what is being optimized before comparing implementations. An algorithmic pattern is a way to structure the proof and computation, not a substitute for either.
| Aspect | Greedy | Dynamic programming |
|---|---|---|
| Construction | Commit to local choices | Reuse subproblem solutions |
| Required argument | Validity of the choice rule | Validity of states and transitions |
| Caution | Largest-first fails on arbitrary coins | Large state spaces can be costly |
Use coin change as a counterexample
Take denominations one, three and four, and minimize the number of coins making six. Choosing the largest available denomination first gives four, then one and one: three coins. Choosing three and three uses two. This counterexample disproves the claim that largest-first works for arbitrary denomination sets. It does not prove that greedy change fails for every currency or every input. Some structured denomination systems admit an optimal greedy strategy, but their conditions need a separate argument. Practical familiarity with one currency is not a proof for arbitrary numerical inputs. A small counterexample is especially valuable because it identifies the exact unsupported step from an attractive local choice to a global conclusion.
Define the state through the final coin
Let dp[x] be the minimum coins needed for amount x, with dp[0]=0. If the last coin has denomination c, the previous coins must make x−c. Minimize dp[x−c]+1 over allowed c. For denominations one, three and four, dp[6] compares dp[5]+1, dp[3]+1 and dp[2]+1. This model assumes nonnegative integer amounts and unlimited reuse of each denomination. Limited supplies require additional state or another update discipline. A recurrence that looks similar can solve a different problem if its assumptions are changed. Write the state meaning in words before implementing the loop, then check that each transition preserves exactly that meaning.
coins, target = [1, 3, 4], 6
inf = target + 1
dp = [0] + [inf] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount and dp[amount - coin] != inf:
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
assert dp[6] == 2
remaining, used = target, 0
for coin in sorted(coins, reverse=True):
used += remaining // coin
remaining %= coin
assert remaining == 0 and used == 3
Represent unreachable states and recover a solution
With only denominations three and four, amounts one and two are unreachable. Representing them as zero coins would let later transitions build false solutions from them. Use a distinct unavailable or infinite state and update only from valid predecessors. If the actual coin selection is needed, record the final coin when a state improves, then walk backward by reducing the amount. Equal-count solutions introduce a separate tie-breaking policy. This applies beyond coin change: the optimum value, existence of a feasible solution and reconstruction of one solution are distinct output requirements. Neither a greedy rule nor a correct numerical recurrence automatically supplies all three without the corresponding representation and boundary handling.
Account for the number and size of states
For k denominations and target amount A, the simple DP takes O(kA) time and O(A) space. Dependence on the numeric value A is not dependence on the binary input length used to encode A. A huge target can therefore make the table impractical, requiring state reduction or other mathematical structure. A proven greedy rule can be much cheaper when its conditions hold. Choose by examining the objective, justification for local choices, information required by a state and the resulting state count. Comparing small instances with exhaustive search can expose a mistaken greedy rule or transition. That experiment complements the proof; it does not establish correctness for every untested input.