Coin Change (Bottom-Up)

Build a one-dimensional table where each amount stores the fewest coins needed to make it.

Algorithm

Steps

Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
Scan amounts from 1 through 6.
For each coin, read the earlier cell dp[amount - coin] when it exists.
Write the smallest candidate into the current amount.
Print both the final answer and the full DP array.

Complexity

Time: O(target * coin_count)
Space: O(target)

bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

Visual walkthrough

Kotlin DSA Implementation

basic.kt

fun listString(values: IntArray): String = values.joinToString(prefix = "[", postfix = "]")

fun main() {
    val coins = intArrayOf(1, 3, 4)
    val target = 6
    val inf = target + 1
    val dp = IntArray(target + 1) { inf }
    dp[0] = 0
    for (amount in 1..target) {
        for (coin in coins) {
            if (amount >= coin) {
                val candidate = dp[amount - coin] + 1
                if (candidate < dp[amount]) dp[amount] = candidate
            }
        }
    }
    println(dp[target])
    println(listString(dp))
}

The pinned coins are [1, 3, 4] and target is 6. The diagrams show the one-dimensional DP table becoming reachable from left to right.

Step 1 - Initialize reachable amount 0

dp[0] = 0; every other amount starts as the sentinel 7.

Step 2 - Early amounts become reachable

With coins 1, 3, and 4, amounts 1 through 4 fill as [1, 2, 1, 1].

Step 3 - Final answer at amount 6

dp[5] = 2 and dp[6] = 2, so the target needs two coins.

Output

2
[0, 1, 2, 1, 1, 2, 2]

Implementation notes

Kotlin stores coins as a primitive IntArray from intArrayOf(1, 3, 4); target, inf, and loop indexes are non-null Int values.
val dp = IntArray(target + 1) { inf } creates a mutable primitive IntArray of length 7, filled with the sentinel target + 1, which is 7.
The dp binding is a val, but its cells mutate in place; dp[0] = 0 creates the traced initial table [0, 7, 7, 7, 7, 7, 7].
The outer loop is for (amount in 1..target), and the inner loop scans for (coin in coins), so each amount considers coins 1, 3, then 4.
if (amount >= coin) guards dp[amount - coin] so indexes never go negative.
The update uses val candidate = dp[amount - coin] + 1 and writes dp[amount] = candidate only when candidate < dp[amount]; there is no separate unreachable-state check in this checked input.
The trace shows dp progressing through [0, 1, 7, 7, 7, 7, 7], [0, 1, 2, 7, 7, 7, 7], [0, 1, 2, 1, 1, 2, 7], and finally [0, 1, 2, 1, 1, 2, 2].
println(dp[target]) prints 2, and println(listString(dp)) formats the full IntArray as [0, 1, 2, 1, 1, 2, 2].