# 518. Coin Change 2 (Unbounded Knapsack problem)
## DFS
```java
class Solution {
public int change(int amount, int[] coins) {
return dfs(amount, coins, 0);
}
private int dfs(int amount, int[] coins, int start) {
if (amount == 0) { // get one way to fit amount
return 1;
}
if (amount < 0) { // no way to fit amount
return 0;
}
int result = 0;
// next round from next start to take coin deno
for (int i = start; i < coins.length; i++) { // notice start, use differnet coins to ...
result += dfs(amount - coins[i], coins, i);
}
return result;
}
}
```
## DFS + memo
```java
class Solution {
public int change(int amount, int[] coins) {
Integer[][] memo = new Integer[amount+1][coins.length];
return dfs(amount, coins, 0, memo);
}
private int dfs(int amount, int[] coins, int start, Integer[][] memo) {
if (amount == 0) { // key point is here!
return 1;
}
if (amount < 0) { // key point is here!
return 0;
}
if (memo[amount][start] != null) {
return memo[amount][start];
}
int result = 0;
for (int i = start; i < coins.length; i++) {
result += dfs(amount - coins[i], coins, i, memo);
}
memo[amount][start] = result;
return memo[amount][start];
}
}
```
上個做法用了 combination 的想法 i = start
也可以這樣做, 這樣做就跟完全背包的概念一樣
```java
class Solution {
public int change(int amount, int[] coins) {
Integer[][] memo = new Integer[amount+1][coins.length];
return dfs(amount, coins, 0, memo);
}
private int dfs(int amount, int[] coins, int start, Integer[][] memo) {
if (amount == 0) { // key point is here!
return 1;
}
if (amount < 0) { // key point is here!
return 0;
}
if (start == coins.length) {
return 0;
}
if (memo[amount][start] != null) {
return memo[amount][start];
}
int result = 0;
result += dfs(amount - coins[start], coins, start, memo) // 選 coin
+ dfs(amount, coins, start+1, memo); // 不選 coin
memo[amount][start] = result;
return memo[amount][start];
}
}
```
start + 1 也可以避開重複使用 coin 的 case
因為我們要的結果是 solutions, 我們要的是 combination, 所以 要避免重複用 1 (以下面的例子來說）
## DP - 2D - Unbounded Knapsack problem
```java
class Solution {
public int change(int amount, int[] coins) {
int m = coins.length;
int n = amount;
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j - coins[i-1] >= 0) {
dp[i][j] = dp[i-1][j] // not choose
+ dp[i][j - coins[i-1]]; // choose
} else {
dp[i][j] = dp[i-1][j]; // j - coins[i-1], not choose
}
}
}
return dp[m][n];
}
}
/*
so use knapsack problem - Unbounded Knapsack problem
choose
or not choose
dp[m][n]: m coins make number of combinations that make up that amount(n), infinite number of each kind of coin
so it'a Unbounded Knapsack problem
m item put into n (weight), m is Unbounded
init case : dp[i][0] = 1;
if (j - coins[i-1] >= 0) {
dp[i][j] = dp[i-1][j] // not choose
+ dp[i][j - coins[i-1]]; // choose
} else {
dp[i][j] = dp[i-1][j]; // j - coins[i-1], not choose
}
TC: O(mn)
SC:O(mn)
*/
```
##
## DP - space 優化到 O(n)
因為`dp` 数组的转移只和 `dp[i][..]` 和 `dp[i-1][..]` 有关, i 和 i -1
from 2D to 1D, 去掉 i 的部分
```java
class Solution {
public int change(int amount, int[] coins) {
int m = coins.length;
int n = amount;
int[] dp = new int[n+1];
dp[0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j - coins[i-1] >= 0) {
dp[j] = dp[j] // not choose
+ dp[j - coins[i-1]]; // choose
}
}
}
return dp[n];
}
}
```
for (int coin : coins) loop 外什麼一定要寫在外層 loop呢？ 為了 排列唯一
那因為 coin 只是遍例, 所以用 for (int coin : coins) 就可以了
dp 部分也可以改成 +=
time: O(coin \* amount)
space: O(amount)
```java
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1; // when amount = 0, there is 1 combination
for (int coin : coins) { // notice coins for loop must be in out loop
for (int i = coin; i <= amount; i++) { // from coin so dont need i >= coin if statement
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}
/*
dp[i]: the number of combinations that make up that amount i.
when choose c from coins[]
dp[i] += dp[i-c]
注意：
for (int coin : coins) { // notice coins for loop must be in out loop
確保整個排列是唯一的方式: coin 在外層 loop
因為 coin 是照順序去組合的, 所以 coins[1, 3, 5]
一定是先做完 1 的排列, 才做3
也就是組合 amount=4, 只會出現, 1,3 , 不會出現 3 1 的組合
*/
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/518.-coin-change-2-unbounded-knapsack-problem.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.