AlgoScope

Coin Change

Fewest coins for amount a = 1 + min over coins c of best(a - c). Ways variant counts combinations.

Dynamic programming, algorithm, intermediate
Amount 1 needs 1 coins.001123456i
Amount 1 needs 1 coins.001123456i

DP in One Row: Fewest coins for 6 from 1, 3, 4

Decision, step 2 of 8

Amount 1. 1: 1 + dp[0] = 1. Keep the smallest: dp[1] = 1, ending with a 1 coin.

How dp in one row works

Cost

Best
O(a * c)
Average
O(a * c)
Worst
O(a * c)
Space
O(a)

Before this

Variants

  • Minimum CoinsMinimize count.
  • Count WaysCount combinations. Iterate coins in the outer loop.

Taught by the same lesson

DP in One Row covers these too, in the same run.