14.5 Unbounded knapsack problem¶
We will now solve another common knapsack variant, unbounded knapsack, and then examine a special case: coin change.
14.5.1 Unbounded knapsack¶
Question
Given \(n\) items, where item \(i\) has weight \(wgt[i-1]\) and value \(val[i-1]\), and a knapsack of capacity \(cap\), each item may be chosen repeatedly. What is the maximum value that fits within the capacity? An example is shown in Figure 14-22.
Figure 14-22 Example input for unbounded knapsack
1. Dynamic programming approach¶
Unbounded knapsack is very similar to 0-1 knapsack. The only difference is that there is no limit on how many times an item may be chosen.
- In 0-1 knapsack, there is only one of each item, so after including item \(i\), we can choose only from the first \(i-1\) items.
- In unbounded knapsack, each item has an unlimited supply, so after including item \(i\), we can still choose from the first \(i\) items.
For unbounded knapsack, state \([i, c]\) has two cases.
- Leave item \(i\) out: As in 0-1 knapsack, the remaining state is \([i-1, c]\).
- Put item \(i\) in: Unlike 0-1 knapsack, the remaining state is \([i, c-wgt[i-1]]\).
The state transition equation becomes:
\[
dp[i, c] = \max(dp[i-1, c], dp[i, c - wgt[i-1]] + val[i-1])
\]
2. Code implementation¶
Compared with 0-1 knapsack, only one \(i-1\) in the transition changes to \(i\); the rest of the code is identical:
unbounded_knapsack.py
def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
"""Unbounded knapsack: dynamic programming"""
n = len(wgt)
# Initialize the dp table
dp = [[0] * (cap + 1) for _ in range(n + 1)]
# State transitions
for i in range(1, n + 1):
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
else:
# Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
return dp[n][cap]
unbounded_knapsack.cpp
/* Unbounded knapsack: dynamic programming */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// Initialize the dp table
vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.java
/* Unbounded knapsack: dynamic programming */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// Initialize the dp table
int[][] dp = new int[n + 1][cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.cs
/* Unbounded knapsack: dynamic programming */
int UnboundedKnapsackDP(int[] wgt, int[] val, int cap) {
int n = wgt.Length;
// Initialize the dp table
int[,] dp = new int[n + 1, cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i, c] = dp[i - 1, c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i, c] = Math.Max(dp[i - 1, c], dp[i, c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n, cap];
}
unbounded_knapsack.go
/* Unbounded knapsack: dynamic programming */
func unboundedKnapsackDP(wgt, val []int, cap int) int {
n := len(wgt)
// Initialize the dp table
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, cap+1)
}
// State transitions
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i-1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i][c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[n][cap]
}
unbounded_knapsack.swift
/* Unbounded knapsack: dynamic programming */
func unboundedKnapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// Initialize the dp table
var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
// State transitions
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[n][cap]
}
unbounded_knapsack.js
/* Unbounded knapsack: dynamic programming */
function unboundedKnapsackDP(wgt, val, cap) {
const n = wgt.length;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.ts
/* Unbounded knapsack: dynamic programming */
function unboundedKnapsackDP(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: cap + 1 }, () => 0)
);
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = Math.max(
dp[i - 1][c],
dp[i][c - wgt[i - 1]] + val[i - 1]
);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.dart
/* Unbounded knapsack: dynamic programming */
int unboundedKnapsackDP(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// Initialize the dp table
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.rs
/* Unbounded knapsack: dynamic programming */
fn unbounded_knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// Initialize the dp table
let mut dp = vec![vec![0; cap + 1]; n + 1];
// State transitions
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = std::cmp::max(dp[i - 1][c], dp[i][c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
return dp[n][cap];
}
unbounded_knapsack.c
/* Unbounded knapsack: dynamic programming */
int unboundedKnapsackDP(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// Initialize the dp table
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(cap + 1, sizeof(int));
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c];
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = myMax(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[n][cap];
// Free memory
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
return res;
}
unbounded_knapsack.kt
/* Unbounded knapsack: dynamic programming */
fun unboundedKnapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
val n = wgt.size
// Initialize the dp table
val dp = Array(n + 1) { IntArray(cap + 1) }
// State transitions
for (i in 1..n) {
for (c in 1..cap) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
} else {
// Take the larger value obtained by excluding and including item i
dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[n][cap]
}
unbounded_knapsack.rb
### Unbounded knapsack: dynamic programming ###
def unbounded_knapsack_dp(wgt, val, cap)
n = wgt.length
# Initialize the dp table
dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
# State transitions
for i in 1...(n + 1)
for c in 1...(cap + 1)
if wgt[i - 1] > c
# If item i exceeds the remaining capacity, do not choose it
dp[i][c] = dp[i - 1][c]
else
# Take the larger value obtained by excluding and including item i
dp[i][c] = [dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[n][cap]
end
Visualize execution
3. Space optimization¶
The current state depends on states to its left and above, so after space optimization, each row of the \(dp\) table must be processed in forward order.
This is the opposite of 0-1 knapsack. Use Figure 14-23 to understand the difference.
Figure 14-23 Space-optimized dynamic programming for unbounded knapsack
The implementation simply removes the first dimension of dp:
unbounded_knapsack.py
def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
"""Unbounded knapsack: space-optimized dynamic programming"""
n = len(wgt)
# Initialize the dp table
dp = [0] * (cap + 1)
# State transitions
for i in range(1, n + 1):
# Traverse in increasing order
for c in range(1, cap + 1):
if wgt[i - 1] > c:
# If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
else:
# Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
return dp[cap]
unbounded_knapsack.cpp
/* Unbounded knapsack: space-optimized dynamic programming */
int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
int n = wgt.size();
// Initialize the dp table
vector<int> dp(cap + 1, 0);
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.java
/* Unbounded knapsack: space-optimized dynamic programming */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
int n = wgt.length;
// Initialize the dp table
int[] dp = new int[cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.cs
/* Unbounded knapsack: space-optimized dynamic programming */
int UnboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {
int n = wgt.Length;
// Initialize the dp table
int[] dp = new int[cap + 1];
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.Max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.go
/* Unbounded knapsack: space-optimized dynamic programming */
func unboundedKnapsackDPComp(wgt, val []int, cap int) int {
n := len(wgt)
// Initialize the dp table
dp := make([]int, cap+1)
// State transitions
for i := 1; i <= n; i++ {
for c := 1; c <= cap; c++ {
if wgt[i-1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
}
}
}
return dp[cap]
}
unbounded_knapsack.swift
/* Unbounded knapsack: space-optimized dynamic programming */
func unboundedKnapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// Initialize the dp table
var dp = Array(repeating: 0, count: cap + 1)
// State transitions
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[cap]
}
unbounded_knapsack.js
/* Unbounded knapsack: space-optimized dynamic programming */
function unboundedKnapsackDPComp(wgt, val, cap) {
const n = wgt.length;
// Initialize the dp table
const dp = Array.from({ length: cap + 1 }, () => 0);
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.ts
/* Unbounded knapsack: space-optimized dynamic programming */
function unboundedKnapsackDPComp(
wgt: Array<number>,
val: Array<number>,
cap: number
): number {
const n = wgt.length;
// Initialize the dp table
const dp = Array.from({ length: cap + 1 }, () => 0);
// State transitions
for (let i = 1; i <= n; i++) {
for (let c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.dart
/* Unbounded knapsack: space-optimized dynamic programming */
int unboundedKnapsackDPComp(List<int> wgt, List<int> val, int cap) {
int n = wgt.length;
// Initialize the dp table
List<int> dp = List.filled(cap + 1, 0);
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
return dp[cap];
}
unbounded_knapsack.rs
/* Unbounded knapsack: space-optimized dynamic programming */
fn unbounded_knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
let n = wgt.len();
// Initialize the dp table
let mut dp = vec![0; cap + 1];
// State transitions
for i in 1..=n {
for c in 1..=cap {
if wgt[i - 1] > c as i32 {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
}
}
}
dp[cap]
}
unbounded_knapsack.c
/* Unbounded knapsack: space-optimized dynamic programming */
int unboundedKnapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
int n = wgtSize;
// Initialize the dp table
int *dp = calloc(cap + 1, sizeof(int));
// State transitions
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c];
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
}
}
int res = dp[cap];
// Free memory
free(dp);
return res;
}
unbounded_knapsack.kt
/* Unbounded knapsack: space-optimized dynamic programming */
fun unboundedKnapsackDPComp(
wgt: IntArray,
_val: IntArray,
cap: Int
): Int {
val n = wgt.size
// Initialize the dp table
val dp = IntArray(cap + 1)
// State transitions
for (i in 1..n) {
for (c in 1..cap) {
if (wgt[i - 1] > c) {
// If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
} else {
// Take the larger value obtained by excluding and including item i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
}
}
}
return dp[cap]
}
unbounded_knapsack.rb
### Unbounded knapsack: space-optimized dynamic programming ###
def unbounded_knapsack_dp_comp(wgt, val, cap)
n = wgt.length
# Initialize the dp table
dp = Array.new(cap + 1, 0)
# State transitions
for i in 1...(n + 1)
# Traverse in increasing order
for c in 1...(cap + 1)
if wgt[i -1] > c
# If item i exceeds the remaining capacity, do not choose it
dp[c] = dp[c]
else
# Take the larger value obtained by excluding and including item i
dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
end
end
end
dp[cap]
end
Visualize execution
14.5.2 Coin change problem¶
Knapsack represents a broad family of dynamic programming problems, with many variants such as coin change.
Question
Given \(n\) coin denominations, where denomination \(i\) has value \(coins[i - 1]\), and a target amount \(amt\), each denomination may be used repeatedly. What is the minimum number of coins needed to make the target? Return \(-1\) if it cannot be made. An example is shown in Figure 14-24.
Figure 14-24 Example input for coin change
1. Dynamic programming approach¶
Coin change can be viewed as a special case of unbounded knapsack, with the following connections and differences.
- The two problems can be translated into one another: items correspond to coins, item weights to coin denominations, and knapsack capacity to the target amount.
- The optimization objectives are opposite: unbounded knapsack maximizes item value, while coin change minimizes the number of coins.
- Unbounded knapsack must stay within a capacity limit, whereas coin change must reach the target amount exactly.
Step 1: Identify each decision, define the state, and establish the \(dp\) table
State \([i, a]\) represents the subproblem of finding the minimum number of coins needed to make amount \(a\) using the first \(i\) denominations, denoted by \(dp[i, a]\).
The two-dimensional \(dp\) table has size \((n+1) \times (amt+1)\).
Step 2: Identify optimal substructure and derive the state transition equation
The state transition differs from unbounded knapsack in two ways.
- We want a minimum, so replace \(\max()\) with \(\min()\).
- We optimize the coin count rather than item value, so choosing a coin adds \(+1\).
\[
dp[i, a] = \min(dp[i-1, a], dp[i, a - coins[i-1]] + 1)
\]
Step 3: Determine the boundary conditions and evaluation order
A target amount of \(0\) requires \(0\) coins, so every entry \(dp[i, 0]\) in the first column is \(0\).
With no coins, any target amount \(> 0\) is impossible. To let \(\min()\) recognize and discard these infeasible solutions, represent them by \(+ \infty\): set the first-row entries \(dp[0, a]\) to \(+ \infty\).
2. Code implementation¶
Most programming languages do not provide an integer value for \(+ \infty\), so the maximum int value is used instead. However, the \(+ 1\) in the transition may then overflow.
Instead, use \(amt + 1\) to represent an infeasible solution, since making \(amt\) requires at most \(amt\) coins. Before returning, check whether \(dp[n, amt]\) equals \(amt + 1\). If so, return \(-1\) to indicate that the target cannot be made. The code is as follows:
coin_change.py
def coin_change_dp(coins: list[int], amt: int) -> int:
"""Coin change: dynamic programming"""
n = len(coins)
MAX = amt + 1
# Initialize the dp table
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# State transitions: first row and first column
for a in range(1, amt + 1):
dp[0][a] = MAX
# State transitions: remaining rows and columns
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# If the coin value exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
else:
# Take the smaller result of not choosing and choosing coin i
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
return dp[n][amt] if dp[n][amt] != MAX else -1
coin_change.cpp
/* Coin change: dynamic programming */
int coinChangeDP(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// Initialize the dp table
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// State transitions: first row and first column
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
coin_change.java
/* Coin change: dynamic programming */
int coinChangeDP(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// Initialize the dp table
int[][] dp = new int[n + 1][amt + 1];
// State transitions: first row and first column
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
coin_change.cs
/* Coin change: dynamic programming */
int CoinChangeDP(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// Initialize the dp table
int[,] dp = new int[n + 1, amt + 1];
// State transitions: first row and first column
for (int a = 1; a <= amt; a++) {
dp[0, a] = MAX;
}
// State transitions: remaining rows and columns
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i, a] = dp[i - 1, a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i, a] = Math.Min(dp[i - 1, a], dp[i, a - coins[i - 1]] + 1);
}
}
}
return dp[n, amt] != MAX ? dp[n, amt] : -1;
}
coin_change.go
/* Coin change: dynamic programming */
func coinChangeDP(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// Initialize the dp table
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// State transitions: first row and first column
for a := 1; a <= amt; a++ {
dp[0][a] = max
}
// State transitions: remaining rows and columns
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[i][a] = dp[i-1][a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = int(math.Min(float64(dp[i-1][a]), float64(dp[i][a-coins[i-1]]+1)))
}
}
}
if dp[n][amt] != max {
return dp[n][amt]
}
return -1
}
coin_change.swift
/* Coin change: dynamic programming */
func coinChangeDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// Initialize the dp table
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// State transitions: first row and first column
for a in 1 ... amt {
dp[0][a] = MAX
}
// State transitions: remaining rows and columns
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1
}
coin_change.js
/* Coin change: dynamic programming */
function coinChangeDP(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// State transitions: first row and first column
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
coin_change.ts
/* Coin change: dynamic programming */
function coinChangeDP(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// State transitions: first row and first column
for (let a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] !== MAX ? dp[n][amt] : -1;
}
coin_change.dart
/* Coin change: dynamic programming */
int coinChangeDP(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// Initialize the dp table
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// State transitions: first row and first column
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
return dp[n][amt] != MAX ? dp[n][amt] : -1;
}
coin_change.rs
/* Coin change: dynamic programming */
fn coin_change_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// Initialize the dp table
let mut dp = vec![vec![0; amt + 1]; n + 1];
// State transitions: first row and first column
for a in 1..=amt {
dp[0][a] = max;
}
// State transitions: remaining rows and columns
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = std::cmp::min(dp[i - 1][a], dp[i][a - coins[i - 1] as usize] + 1);
}
}
}
if dp[n][amt] != max {
return dp[n][amt] as i32;
} else {
-1
}
}
coin_change.c
/* Coin change: dynamic programming */
int coinChangeDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// Initialize the dp table
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// State transitions: first row and first column
for (int a = 1; a <= amt; a++) {
dp[0][a] = MAX;
}
// State transitions: remaining rows and columns
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = myMin(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
}
}
}
int res = dp[n][amt] != MAX ? dp[n][amt] : -1;
// Free memory
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
coin_change.kt
/* Coin change: dynamic programming */
fun coinChangeDP(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// Initialize the dp table
val dp = Array(n + 1) { IntArray(amt + 1) }
// State transitions: first row and first column
for (a in 1..amt) {
dp[0][a] = MAX
}
// State transitions: remaining rows and columns
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// If the coin value exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)
}
}
}
return if (dp[n][amt] != MAX) dp[n][amt] else -1
}
coin_change.rb
### Coin change: dynamic programming ###
def coin_change_dp(coins, amt)
n = coins.length
_MAX = amt + 1
# Initialize the dp table
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# State transitions: first row and first column
(1...(amt + 1)).each { |a| dp[0][a] = _MAX }
# State transitions: remaining rows and columns
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# If the coin exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
else
# Take the smaller result of not choosing and choosing coin i
dp[i][a] = [dp[i - 1][a], dp[i][a - coins[i - 1]] + 1].min
end
end
end
dp[n][amt] != _MAX ? dp[n][amt] : -1
end
Visualize execution
Figure 14-25 shows dynamic programming for coin change, which closely resembles unbounded knapsack.
Figure 14-25 Dynamic programming for coin change
3. Space optimization¶
Space optimization is the same as for unbounded knapsack:
coin_change.py
def coin_change_dp_comp(coins: list[int], amt: int) -> int:
"""Coin change: space-optimized dynamic programming"""
n = len(coins)
MAX = amt + 1
# Initialize the dp table
dp = [MAX] * (amt + 1)
dp[0] = 0
# State transitions
for i in range(1, n + 1):
# Traverse in increasing order
for a in range(1, amt + 1):
if coins[i - 1] > a:
# If the coin value exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
else:
# Take the smaller result of not choosing and choosing coin i
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
return dp[amt] if dp[amt] != MAX else -1
coin_change.cpp
/* Coin change: space-optimized dynamic programming */
int coinChangeDPComp(vector<int> &coins, int amt) {
int n = coins.size();
int MAX = amt + 1;
// Initialize the dp table
vector<int> dp(amt + 1, MAX);
dp[0] = 0;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
coin_change.java
/* Coin change: space-optimized dynamic programming */
int coinChangeDPComp(int[] coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// Initialize the dp table
int[] dp = new int[amt + 1];
Arrays.fill(dp, MAX);
dp[0] = 0;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
coin_change.cs
/* Coin change: space-optimized dynamic programming */
int CoinChangeDPComp(int[] coins, int amt) {
int n = coins.Length;
int MAX = amt + 1;
// Initialize the dp table
int[] dp = new int[amt + 1];
Array.Fill(dp, MAX);
dp[0] = 0;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = Math.Min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
coin_change.go
/* Coin change: dynamic programming */
func coinChangeDPComp(coins []int, amt int) int {
n := len(coins)
max := amt + 1
// Initialize the dp table
dp := make([]int, amt+1)
for i := 1; i <= amt; i++ {
dp[i] = max
}
// State transitions
for i := 1; i <= n; i++ {
// Traverse in increasing order
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = int(math.Min(float64(dp[a]), float64(dp[a-coins[i-1]]+1)))
}
}
}
if dp[amt] != max {
return dp[amt]
}
return -1
}
coin_change.swift
/* Coin change: space-optimized dynamic programming */
func coinChangeDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
let MAX = amt + 1
// Initialize the dp table
var dp = Array(repeating: MAX, count: amt + 1)
dp[0] = 0
// State transitions
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return dp[amt] != MAX ? dp[amt] : -1
}
coin_change.js
/* Coin change: space-optimized dynamic programming */
function coinChangeDPComp(coins, amt) {
const n = coins.length;
const MAX = amt + 1;
// Initialize the dp table
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
coin_change.ts
/* Coin change: space-optimized dynamic programming */
function coinChangeDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
const MAX = amt + 1;
// Initialize the dp table
const dp = Array.from({ length: amt + 1 }, () => MAX);
dp[0] = 0;
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] !== MAX ? dp[amt] : -1;
}
coin_change.dart
/* Coin change: space-optimized dynamic programming */
int coinChangeDPComp(List<int> coins, int amt) {
int n = coins.length;
int MAX = amt + 1;
// Initialize the dp table
List<int> dp = List.filled(amt + 1, MAX);
dp[0] = 0;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the current amount a, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
return dp[amt] != MAX ? dp[amt] : -1;
}
coin_change.rs
/* Coin change: space-optimized dynamic programming */
fn coin_change_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
let max = amt + 1;
// Initialize the dp table
let mut dp = vec![0; amt + 1];
dp.fill(max);
dp[0] = 0;
// State transitions
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = std::cmp::min(dp[a], dp[a - coins[i - 1] as usize] + 1);
}
}
}
if dp[amt] != max {
return dp[amt] as i32;
} else {
-1
}
}
coin_change.c
/* Coin change: space-optimized dynamic programming */
int coinChangeDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
int MAX = amt + 1;
// Initialize the dp table
int *dp = malloc((amt + 1) * sizeof(int));
for (int j = 1; j <= amt; j++) {
dp[j] = MAX;
}
dp[0] = 0;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = myMin(dp[a], dp[a - coins[i - 1]] + 1);
}
}
}
int res = dp[amt] != MAX ? dp[amt] : -1;
// Free memory
free(dp);
return res;
}
coin_change.kt
/* Coin change: space-optimized dynamic programming */
fun coinChangeDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
val MAX = amt + 1
// Initialize the dp table
val dp = IntArray(amt + 1)
dp.fill(MAX)
dp[0] = 0
// State transitions
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// If the coin value exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Take the smaller result of not choosing and choosing coin i
dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
}
}
}
return if (dp[amt] != MAX) dp[amt] else -1
}
coin_change.rb
### Coin change: space-optimized dynamic programming ###
def coin_change_dp_comp(coins, amt)
n = coins.length
_MAX = amt + 1
# Initialize the dp table
dp = Array.new(amt + 1, _MAX)
dp[0] = 0
# State transitions
for i in 1...(n + 1)
# Traverse in increasing order
for a in 1...(amt + 1)
if coins[i - 1] > a
# If the coin exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
else
# Take the smaller result of not choosing and choosing coin i
dp[a] = [dp[a], dp[a - coins[i - 1]] + 1].min
end
end
end
dp[amt] != _MAX ? dp[amt] : -1
end
Visualize execution
14.5.3 Coin change problem II¶
Question
Given \(n\) coin denominations, where denomination \(i\) has value \(coins[i - 1]\), and a target amount \(amt\), each denomination may be used repeatedly. How many combinations of coins make the target amount? An example is shown in Figure 14-26.
Figure 14-26 Example input for coin change II
1. Dynamic programming approach¶
This time, we count combinations, so the subproblem becomes the number of combinations that make amount \(a\) using the first \(i\) denominations. The \(dp\) table remains a two-dimensional matrix of size \((n+1) \times (amt + 1)\).
The number of combinations for the current state is the sum of those that exclude the current coin and those that include it. The state transition equation is:
\[
dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]]
\]
A target of \(0\) can be made by choosing no coins, so initialize every first-column entry \(dp[i, 0]\) to \(1\). With no coins, any target \(>0\) is impossible, so the first-row entries \(dp[0, a]\) are \(0\).
2. Code implementation¶
coin_change_ii.py
def coin_change_ii_dp(coins: list[int], amt: int) -> int:
"""Coin change II: dynamic programming"""
n = len(coins)
# Initialize the dp table
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# Initialize the first column
for i in range(n + 1):
dp[i][0] = 1
# State transitions
for i in range(1, n + 1):
for a in range(1, amt + 1):
if coins[i - 1] > a:
# If the coin value exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
else:
# Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
return dp[n][amt]
coin_change_ii.cpp
/* Coin change II: dynamic programming */
int coinChangeIIDP(vector<int> &coins, int amt) {
int n = coins.size();
// Initialize the dp table
vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
// Initialize the first column
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
coin_change_ii.java
/* Coin change II: dynamic programming */
int coinChangeIIDP(int[] coins, int amt) {
int n = coins.length;
// Initialize the dp table
int[][] dp = new int[n + 1][amt + 1];
// Initialize the first column
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
coin_change_ii.cs
/* Coin change II: dynamic programming */
int CoinChangeIIDP(int[] coins, int amt) {
int n = coins.Length;
// Initialize the dp table
int[,] dp = new int[n + 1, amt + 1];
// Initialize the first column
for (int i = 0; i <= n; i++) {
dp[i, 0] = 1;
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i, a] = dp[i - 1, a];
} else {
// Add the numbers of ways without and with coin i
dp[i, a] = dp[i - 1, a] + dp[i, a - coins[i - 1]];
}
}
}
return dp[n, amt];
}
coin_change_ii.go
/* Coin change II: dynamic programming */
func coinChangeIIDP(coins []int, amt int) int {
n := len(coins)
// Initialize the dp table
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amt+1)
}
// Initialize the first column
for i := 0; i <= n; i++ {
dp[i][0] = 1
}
// State transitions: remaining rows and columns
for i := 1; i <= n; i++ {
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[i][a] = dp[i-1][a]
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]
}
}
}
return dp[n][amt]
}
coin_change_ii.swift
/* Coin change II: dynamic programming */
func coinChangeIIDP(coins: [Int], amt: Int) -> Int {
let n = coins.count
// Initialize the dp table
var dp = Array(repeating: Array(repeating: 0, count: amt + 1), count: n + 1)
// Initialize the first column
for i in 0 ... n {
dp[i][0] = 1
}
// State transitions
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
coin_change_ii.js
/* Coin change II: dynamic programming */
function coinChangeIIDP(coins, amt) {
const n = coins.length;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// Initialize the first column
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
coin_change_ii.ts
/* Coin change II: dynamic programming */
function coinChangeIIDP(coins: Array<number>, amt: number): number {
const n = coins.length;
// Initialize the dp table
const dp = Array.from({ length: n + 1 }, () =>
Array.from({ length: amt + 1 }, () => 0)
);
// Initialize the first column
for (let i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
coin_change_ii.dart
/* Coin change II: dynamic programming */
int coinChangeIIDP(List<int> coins, int amt) {
int n = coins.length;
// Initialize the dp table
List<List<int>> dp = List.generate(n + 1, (index) => List.filled(amt + 1, 0));
// Initialize the first column
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
return dp[n][amt];
}
coin_change_ii.rs
/* Coin change II: dynamic programming */
fn coin_change_ii_dp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// Initialize the dp table
let mut dp = vec![vec![0; amt + 1]; n + 1];
// Initialize the first column
for i in 0..=n {
dp[i][0] = 1;
}
// State transitions
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1] as usize];
}
}
}
dp[n][amt]
}
coin_change_ii.c
/* Coin change II: dynamic programming */
int coinChangeIIDP(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// Initialize the dp table
int **dp = malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++) {
dp[i] = calloc(amt + 1, sizeof(int));
}
// Initialize the first column
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[i][a] = dp[i - 1][a];
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
}
}
}
int res = dp[n][amt];
// Free memory
for (int i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
coin_change_ii.kt
/* Coin change II: dynamic programming */
fun coinChangeIIDP(coins: IntArray, amt: Int): Int {
val n = coins.size
// Initialize the dp table
val dp = Array(n + 1) { IntArray(amt + 1) }
// Initialize the first column
for (i in 0..n) {
dp[i][0] = 1
}
// State transitions
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// If the coin value exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
} else {
// Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
}
}
}
return dp[n][amt]
}
coin_change_ii.rb
### Coin change II: dynamic programming ###
def coin_change_ii_dp(coins, amt)
n = coins.length
# Initialize the dp table
dp = Array.new(n + 1) { Array.new(amt + 1, 0) }
# Initialize the first column
(0...(n + 1)).each { |i| dp[i][0] = 1 }
# State transitions
for i in 1...(n + 1)
for a in 1...(amt + 1)
if coins[i - 1] > a
# If the coin exceeds the current amount a, do not choose coin i
dp[i][a] = dp[i - 1][a]
else
# Add the numbers of ways without and with coin i
dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
end
end
end
dp[n][amt]
end
Visualize execution
3. Space optimization¶
The space optimization is the same: remove the coin dimension:
coin_change_ii.py
def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
"""Coin change II: space-optimized dynamic programming"""
n = len(coins)
# Initialize the dp table
dp = [0] * (amt + 1)
dp[0] = 1
# State transitions
for i in range(1, n + 1):
# Traverse in increasing order
for a in range(1, amt + 1):
if coins[i - 1] > a:
# If the coin value exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
else:
# Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]]
return dp[amt]
coin_change_ii.cpp
/* Coin change II: space-optimized dynamic programming */
int coinChangeIIDPComp(vector<int> &coins, int amt) {
int n = coins.size();
// Initialize the dp table
vector<int> dp(amt + 1, 0);
dp[0] = 1;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.java
/* Coin change II: space-optimized dynamic programming */
int coinChangeIIDPComp(int[] coins, int amt) {
int n = coins.length;
// Initialize the dp table
int[] dp = new int[amt + 1];
dp[0] = 1;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.cs
/* Coin change II: space-optimized dynamic programming */
int CoinChangeIIDPComp(int[] coins, int amt) {
int n = coins.Length;
// Initialize the dp table
int[] dp = new int[amt + 1];
dp[0] = 1;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.go
/* Coin change II: space-optimized dynamic programming */
func coinChangeIIDPComp(coins []int, amt int) int {
n := len(coins)
// Initialize the dp table
dp := make([]int, amt+1)
dp[0] = 1
// State transitions
for i := 1; i <= n; i++ {
// Traverse in increasing order
for a := 1; a <= amt; a++ {
if coins[i-1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a-coins[i-1]]
}
}
}
return dp[amt]
}
coin_change_ii.swift
/* Coin change II: space-optimized dynamic programming */
func coinChangeIIDPComp(coins: [Int], amt: Int) -> Int {
let n = coins.count
// Initialize the dp table
var dp = Array(repeating: 0, count: amt + 1)
dp[0] = 1
// State transitions
for i in 1 ... n {
for a in 1 ... amt {
if coins[i - 1] > a {
// If the coin exceeds the current target amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
coin_change_ii.js
/* Coin change II: space-optimized dynamic programming */
function coinChangeIIDPComp(coins, amt) {
const n = coins.length;
// Initialize the dp table
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.ts
/* Coin change II: space-optimized dynamic programming */
function coinChangeIIDPComp(coins: Array<number>, amt: number): number {
const n = coins.length;
// Initialize the dp table
const dp = Array.from({ length: amt + 1 }, () => 0);
dp[0] = 1;
// State transitions
for (let i = 1; i <= n; i++) {
for (let a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.dart
/* Coin change II: space-optimized dynamic programming */
int coinChangeIIDPComp(List<int> coins, int amt) {
int n = coins.length;
// Initialize the dp table
List<int> dp = List.filled(amt + 1, 0);
dp[0] = 1;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the current amount a, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
return dp[amt];
}
coin_change_ii.rs
/* Coin change II: space-optimized dynamic programming */
fn coin_change_ii_dp_comp(coins: &[i32], amt: usize) -> i32 {
let n = coins.len();
// Initialize the dp table
let mut dp = vec![0; amt + 1];
dp[0] = 1;
// State transitions
for i in 1..=n {
for a in 1..=amt {
if coins[i - 1] > a as i32 {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1] as usize];
}
}
}
dp[amt]
}
coin_change_ii.c
/* Coin change II: space-optimized dynamic programming */
int coinChangeIIDPComp(int coins[], int amt, int coinsSize) {
int n = coinsSize;
// Initialize the dp table
int *dp = calloc(amt + 1, sizeof(int));
dp[0] = 1;
// State transitions
for (int i = 1; i <= n; i++) {
for (int a = 1; a <= amt; a++) {
if (coins[i - 1] > a) {
// If the coin exceeds the target amount, do not choose coin i
dp[a] = dp[a];
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]];
}
}
}
int res = dp[amt];
// Free memory
free(dp);
return res;
}
coin_change_ii.kt
/* Coin change II: space-optimized dynamic programming */
fun coinChangeIIDPComp(coins: IntArray, amt: Int): Int {
val n = coins.size
// Initialize the dp table
val dp = IntArray(amt + 1)
dp[0] = 1
// State transitions
for (i in 1..n) {
for (a in 1..amt) {
if (coins[i - 1] > a) {
// If the coin value exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
} else {
// Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]]
}
}
}
return dp[amt]
}
coin_change_ii.rb
### Coin change II: space-optimized dynamic programming ###
def coin_change_ii_dp_comp(coins, amt)
n = coins.length
# Initialize the dp table
dp = Array.new(amt + 1, 0)
dp[0] = 1
# State transitions
for i in 1...(n + 1)
# Traverse in increasing order
for a in 1...(amt + 1)
if coins[i - 1] > a
# If the coin exceeds the current amount a, do not choose coin i
dp[a] = dp[a]
else
# Add the numbers of ways without and with coin i
dp[a] = dp[a] + dp[a - coins[i - 1]]
end
end
end
dp[amt]
end