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

Rust DSA Implementation

basic.rs

fn list_string(values: &[i32]) -> String {
    format!("[{}]", values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", "))
}

fn main() {
    let coins = [1, 3, 4];
    let target = 6usize;
    let inf = (target + 1) as i32;
    let mut dp = vec![inf; target + 1];
    dp[0] = 0;
    for amount in 1..=target {
        for coin in coins {
            let coin = coin as usize;
            if amount >= coin {
                let candidate = dp[amount - coin] + 1;
                if candidate < dp[amount] {
                    dp[amount] = candidate;
                }
            }
        }
    }
    println!("{}", dp[target]);
    println!("{}", list_string(&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

coins is a fixed [i32; 3] array, while target is 6usize so it can be used directly for vector lengths and indexes.
let inf = (target + 1) as i32 creates the unreachable sentinel 7, and vec![inf; target + 1] initializes dp: Vec<i32> as [7, 7, 7, 7, 7, 7, 7] before dp[0] = 0.
The outer loop scans amounts with for amount in 1..=target; the inner loop copies each coin value and casts it with let coin = coin as usize before indexing dp[amount - coin].
if amount >= coin guards the subtraction and vector access. The update is explicit: candidate = dp[amount - coin] + 1, then replace dp[amount] only when candidate < dp[amount].
The fixed input always reaches every amount, so the source prints dp[target] directly and does not convert the sentinel to a separate impossible value.
The trace shows dp moving from [0, 7, 7, 7, 7, 7, 7] through [0, 1, 2, 1, 1, 2, 2], with amount 6 choosing coin 3 -> 2.
println!("{}", dp[target]) prints 2, then list_string(&dp) borrows the table and println!("{}", ...) prints [0, 1, 2, 1, 1, 2, 2].