Unbounded & Coin-Change DP
Use items any number of times.
Unbounded & Coin-Change DP is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Unlimited Items
In the unbounded knapsack, each item can be taken as many times as you like. Think of coins in a vending machine, not a fixed pile.
The One Tiny Change
Compared to 0/1, only the loop direction flips. For unbounded items you iterate capacity forward, low to high.
Forward Reuse Is the Point
Going forward, dp[w - coin] may already include this same item. That intentional reuse is exactly what lets you take it again.
Meet Coin Change
The classic coin change asks for the fewest coins that sum to an amount. It is unbounded DP with a min instead of a max.
Define the State
Let dp[a] be the fewest coins needed to make amount a. Start by seeding dp[0] = 0 since zero needs no coins.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Use Infinity for Impossible
Unreachable amounts start as infinity. If an amount stays infinite at the end, no combination of coins can build it.
The Transition
For each coin, try improving every amount it can reach. Use one more coin than the smaller amount left behind.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Why Forward Order
Sweeping amounts upward lets dp[a - coin] already count this coin. That is how a single coin contributes multiple times.
Counting Ways Instead
Swap min+1 for a sum to count the number of ways to make each amount. Coin loop outside avoids counting orderings twice.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Read the Result
Your answer lives in dp[amount]. For the min version, an infinite value means the target is impossible to form.
0/1 vs Unbounded
Remember the one switch: backward capacity means each item once, forward means unlimited. Same table, opposite sweep.
Quick Check
Test what makes knapsack unbounded.
Recap
You flipped the loop forward for unlimited reuse and built coin change with min for fewest coins or sum for total ways. 💰
Frequently asked questions
Is the “Unbounded & Coin-Change DP” lesson free?
Yes — the full text of “Unbounded & Coin-Change DP” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Unbounded & Coin-Change DP”?
Use items any number of times. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Unbounded & Coin-Change DP” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- 0/1 Knapsack: Take or Leave
- Space-Optimized Knapsack
- Unbounded & Coin-Change DP
- Subset Sum & Partition