Classic DP: Unbounded Knapsack Problem

LeetCode Problem 322 "Coin Change I" is discussed as a classic dynamic programming example in Detailed Explanation of Dynamic Programming Techniques. This article discusses "Coin Change II," which is another typical variant of the knapsack problem. Previously, we have covered Classic Dynamic Programming: 0-1 Knapsack Problem and Knapsack Problem Variant: Equal Subset Partition.

Before reading this article, it is recommended that you have read the previous two articles, which cover dynamic programming and knapsack problem techniques. This article will continue the knapsack problem approach, presenting a variation of the knapsack problem.

Let's look at LeetCode Problem 518 "Coin Change II":

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Input: amount = 10, coins = [10]
Output: 1

The function signature we need to complete is as follows:

int change(int amount, int[] coins);

int change(int amount, vector<int>& coins);

def change(amount: int, coins: List[int]) -> int:

func change(amount int, coins []int) int

var change = function(amount, coins) {

};

We can transform this problem into the description of a knapsack problem:

Imagine a knapsack with a maximum capacity of amount. There is a series of items coins, where each item has a weight of coins[i]. The quantity of each item is unlimited. The question is, how many ways are there to fill the knapsack exactly?

This problem differs from the two knapsack problems we discussed earlier in one major aspect: the quantity of each item is unlimited. This is known as the "unbounded knapsack problem". It's not very complex; the main difference lies in the state transition equation.

Let's continue the analysis following the knapsack problem's description.