CoinChange [钱币兑换]
# 介绍
给出一个大小为 N 的硬币的整数数组 coins [] ，代表不同类型的货币和一个整数的总和 sum，任务是通过使用硬币的不同组合来找出求和的方法。
# 递归法
应用递归来遍历数组，并不断寻找可能的方式来找到出现的情况。
遵循以下步骤：
- 对于一个特定面额的硬币，我们有两个选择，一是包括，二是排除。
- 如果我们在
coins[n-1]，我们可以尽可能多地选择该硬币的实例（无限制的包含），即count(coins, n, sum - coins[n-1])；然后我们移动到coins[n-2]。 - 在移动到硬币
[n-2]之后，我们不能再往回移动，也不能对硬币[n-1]进行选择，即count(coins, n-1, sum)。 - 最后，由于我们要找出总的方法，所以我们要把这两个可能的选择加起来，即
count(coins, n, sum - coins[n-1] ) + count(coins, n-1, sum )。
JavaScript：
// Returns the count of ways we can sum coins[0...n-1] coins to get sum "sum"
function count(coins , n , sum ) {
// If sum is 0 then there is 1 solution (do not include any coin)
if (sum == 0) return 1;
// If sum is less than 0 then no solution exists
if (sum < 0) return 0;
// If there are no coins and sum is greater than 0, then no solution exist
if (n <=0) return 0;
// count is sum of solutions (i) including coins[n-1] (ii) excluding coins[n-1]
return count( coins, n - 1, sum ) + count( coins, n, sum - coins[n - 1] );
}
// Driver program to test above function
var coins = [1, 2, 3];
var n = coins.length;
document.write( count(coins, n, 4));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 时间复杂度：O (2sum)
- 辅助空间：O (target)
由于相同的子问题被再次调用，这个问题具有重叠子问题的特性。所以硬币变化问题具有动态规划问题的两个属性。像其他典型的动态编程 (DP) 问题一样，可以通过自下而上的方式构造一个临时数组表来避免相同子问题的重新计算。
# 动态规划法
解决这个问题的想法是通过使用自下而上的记忆法（Bottom Up Memoization）。以下是解决这个问题的自下而上的方法。
按照下面的步骤：
- 使用二维矢量来存储重叠的子问题（Overlapping subproblems）。
- 遍历整个数组以找到解决方案并存储在缓存表（memoization table）中。
- 使用缓存表来寻找最佳解决方案。
JavaScript：
/* Dynamic Programming javascript implementation of Coin Change problem */
function countWays(coins , n , sum) {
// table[i] will be storing the number of solutions for value i. We need sum+1 rows as the table is
// constructed in bottom up manner using the base case (sum = 0)
// Initialize all table values as 0
const table = Array(sum+1).fill(0);
// Base case (If given value is 0)
table[0] = 1;
// Pick all coins one by one and update the table values after the index greater than or equal to the value of the picked coin
for (i=0; i<n; i++)
for (j=coins[i]; j<=sum; j++)
table[j] += table[j-coins[i]];
return table[sum];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
或者：
/**
* @params {Array} coins
* @params {Number} amount
*/
const change = (coins, amount) => {
// Create and initialize the storage
const combinations = new Array(amount + 1).fill(0)
combinations[0] = 1
// Determine the direction of smallest sub-problem
for (let i = 0; i < coins.length; i++) {
// Travel and fill the combinations array
for (let j = coins[i]; j < combinations.length; j++) {
combinations[j] += combinations[j - coins[i]]
}
}
return combinations[amount]
}
/**
* @params {Array} coins
* @params {Number} amount
*/
export const coinChangeMin = (coins, amount) => {
const map = { 0: 1 }
for (let i = 1; i <= amount; i++) {
let min = Infinity
for (const coin of coins) {
if (i < coin) continue
min = Math.min(min, 1 + map[i - coin])
}
map[i] = min
}
return map[amount] === Infinity ? -1 : map[amount] - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 应用
给定不同面值的硬币和总金额，你必须返回组成该金额所需的最少的硬币，如果不可能组成该金额，则返回 - 1。注意，我们有无限量的每种类型的硬币。
递归法：
检查每个硬币组合的给定金额。在这种方法中，我们可以使用递归来解决这个问题，因为我们必须遍历所有可能的硬币组合，每次都要更新产生这个总和所需的最小硬币数量。
int coinChange(vector<int> const &S, int sum) {
if (sum == 0) return 0;
if (sum < 0) return INT_MAX;
int coins = INT_MAX;
for (int i: S) {
int result = coinChange(S, sum - i);
if (result != INT_MAX) coins = min(coins, result + 1);
}
return coins;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
动态规划法：
由于该问题可以被分解成更小的子问题，因为在递归树中有许多重叠的子问题，我们将避免重复解决这些问题。我们采用自下而上的方法，即先解决小问题，然后从小问题转到较大的子问题，因为我们将计算 dp[i] (1<=i<=subproblems)，将答案存储为创建和所需的最少硬币。
int coinChange(vector<int> const &arr, int sum) {
int dp[sum + 1];
for (int i = 1; i <= sum; i++) {
dp[i] = INT_MAX;
int result = INT_MAX;
for (int c: arr) {
if (i - c >= 0) result = dp[i - c];
if (result != INT_MAX) dp[i] = min(dp[i], result + 1);
}
}
return dp[sum];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 参考
编辑 (opens new window)
上次更新: 2022/10/25, 20:46:09