Unbounded & Coin-Change DP
Use items any number of times.
Unbounded & Coin-Change DP is a free Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy course, upgrade to CoddyKit PRO.
What will I learn in “Unbounded & Coin-Change DP”?
Use items any number of times. You practise Competitive Programming Academy 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 Competitive Programming Academy?
No prior experience is required. Competitive Programming Academy 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 Competitive Programming Academy lesson?
Yes. Every Competitive Programming Academy 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