This is the unbounded knapsack family of dynamic programming: minimum-coin change. Each coin denomination may be reused any number of times, so the DP table has one row per coin type considered so far and one column per amount from 0 up to the target β a genuinely different recurrence from 0/1 knapsack (which forbids reuse and appears elsewhere on this site) and from sequence-alignment DP (which compares two strings).
dp[0][0] = 0, dp[0][a>0] = β
dp[i][a] = min( dp[i-1][a], // skip coin i
dp[i][a-coinα΅’] + 1 ) // reuse coin i
answer = dp[n][target]
- Rows (coins considered) β after row i, the table only "knows about" the first i denominations.
- Columns (amount) β the sub-problem "make exactly this amount" with the coins available so far.
- Bar height β the minimum number of coins needed for that sub-problem; a flat red marker means the amount is unreachable with those coins.
- Backtrace (green path) β after the table is full, walking backward from dp[n][target] recovers one exact optimal multiset of coins, which lights up in the coin row.
- Greedy β always grabbing the largest coin that still fits is fast but not always optimal: with coins {1,3,4} and target 6, greedy picks 4+1+1 (3 coins) while DP finds 3+3 (2 coins).