Leetcode-322. 零钱兑换

描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

1
2
输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

来源:力扣(LeetCode)
链接:322. Coin Change

解题思路

关于这道题, 这个题解给出了非常详细的描述, 从动态规划的基本思路开始, 一步步怎么从暴力方法到到备忘录的递归再到迭代的动态规划, 深入浅出, 图文并茂, 是不可多得的题解.

首先来看暴力解法, 最困难得一步, 就是写出状态转移方程, 这个问题的状态转移方程如下:

附图来自题解,原作者公众号labuladong,欢迎大家关注。

其实,这个方程就用到了「最优子结构」性质:原问题的解由子问题的最优解构成。即 f(11) 由 f(10), f(9), f(6) 的最优解转移而来。

具体代码见解法一。

画出递归树:

时间复杂度分析:递归的总时间是子问题总数 x 每个子问题的时间。子问题总数为递归树节点个数,这个比较难看出来,是$O(N^k)$,总之是指数级别。每个子问题当中还有一个 for 循环,复杂度为$O(k)$,所以最终依然还是指数级别。

下面给递归的解法加一个记忆数组,将中间的计算结果进行保存,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数。这个思路跟Leetcode-139. 单词拆分的解法是类似的。

如果要加入记忆数组,通常的做法是在主调用函数当中什么记忆数组并进行初始化,然后在递归函数当中加入一个记忆数组的变量,因为最后记忆数组是要返回的,需要以指针或者引用的方式进行传参。

具体代码见解法二。

最后再来看看动态规划的解法。

我们维护一个一维动态数组dp,其中dp[i] 表示钱数为i时的最小硬币数的找零,注意由于数组是从0开始的,所以要多申请一位,数组大小为 amount + 1,这样最终结果就可以保存在 dp[amount]中。

初始化 dp[0] = 0,因为目标值若为0时,就不需要任何硬币。其他值可以初始化是 amount + 1,因为最小的硬币是1,所以 amount 最多需要 amount 个硬币,amount + 1 也就相当于当前的最大值了,注意这里不能用整型最大值来初始化,因为在后面的状态转移方程有加1的操作,有可能会溢出.

好,接下来就是要找状态转移方程了。我们先回归例子1,假设我取了一个值为5的硬币,那么由于目标值是 11,所以是不是假如我们知道 dp[6],那么就知道了组成 11 的dp值了?所以更新 dp[i] 的方法就是遍历每个硬币,如果遍历到的硬币值小于i值(比如不能用值为5的硬币去更新 dp[3])时,用 dp[i - coins[j]] + 1 来更新 dp[i],所以状态转移方程为:

$$dp[i] = min(dp[i], dp[i - coins[j]] + 1)$$

其中 coins[j] 为第j个硬币,而 i - coins[j] 为钱数i减去其中一个硬币的值,剩余的钱数在 dp数组中找到值,然后加1和当前 dp 数组中的值做比较,取较小的那个更新 dp数组。

具体代码见解法三。

代码

解法一

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
34
35
36
37
int min (int a, int b)
{
if(a > b)
return b;
else
return a;
}

int coinChange(int* coins, int coinsSize, int amount)
{
//金额为0 返回0
if(amount == 0)
return 0;

int ans = INT_MAX;


for (int i = 0; i < coinsSize; i++)
{
//金额比当前硬币面额小,换一个硬币
if (amount - coins[i] < 0)
continue;

//递归调用,去掉当前可用硬币,因为硬皮可重复使用 *coins变量不变
int tmp = coinChange(coins, coinsSize, amount - coins[i]);

//如果子问题无解,换一个硬币
if (tmp == -1)
continue;

//利用状态转移方程更新
ans = min(ans, tmp + 1);
}

return ans == INT_MAX ? -1 : ans;

}

解法二

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
34
35
36
37
38
39
40
41
42
43
44
int min (int a, int b)
{
if(a > b)
return b;
else
return a;
}

int coinChangeSolver(int* coins, int coinsSize, int target, int *memo)
{
if(target < 0)
return -1;

if(memo[target] != INT_MAX)
return memo[target];

for (int i = 0; i < coinsSize; i++)
{
//计算子问题的解
int tmp = coinChangeSolver(coins, coinsSize, target - coins[i], memo);

//如果子问题有解,更新答案
if (tmp >= 0)
memo[target] = min(memo[target], tmp + 1);
}

//记录并返回本轮答案
return memo[target] = (memo[target] == INT_MAX) ? -1 : memo[target];

}

int coinChange(int* coins, int coinsSize, int amount)
{
//记忆数组初始化为INT_MAX
int memo[amount + 1];
memo[0] = 0;

for (int i = 1; i <= amount; i++)
memo[i] = INT_MAX;


return coinChangeSolver(coins, coinsSize, amount, memo);

}

解法三

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
34
int min (int a, int b)
{
if(a > b)
return b;
else
return a;
}



int coinChange(int* coins, int coinsSize, int amount)
{

//dp数组初始化
int dp[amount + 1];
dp[0] = 0;

for (int i = 1; i <= amount; i++)
dp[i] = amount + 1;

for(int i = 1; i <= amount; i++)
{
for(int j = 0; j < coinsSize; j++)
{
if(coins[j] <= i)
{
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}

return (dp[amount] > amount) ? -1 : dp[amount];

}

参考