Comparisons and explanations · Intermediate

Greedy methods versus dynamic programming

Use a coin-change counterexample and recurrence to distinguish irreversible local choices from reusing solutions to subproblems.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Compare a choice rule with a decomposition strategy
  2. Use coin change as a counterexample
  3. Define the state through the final coin
  4. Represent unreachable states and recover a solution
  5. Account for the number and size of states
  6. Ask Logeia about this articleCheck your understanding

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.

AspectGreedyDynamic programming
ConstructionCommit to local choicesReuse subproblem solutions
Required argumentValidity of the choice ruleValidity of states and transitions
CautionLargest-first fails on arbitrary coinsLarge 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.

Python
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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path