换钱的最小货币数
一、题目
给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数 aim 代表要找的钱数，求组成 aim 的最少货币数
举例：
1
2
3
4
5
6
| arr[5, 2, 3], aim=20
4 张 5 元可以组成 20 元，其他的找钱方案都要使用更多张的货币，所以返回 4
arr[5,2,3], aim=0
不用任何货币就可以组成 0 元，返回 0
arr[3,5], aim=2
根本无法组成 2 元，钱不能找开的情况下默认返回 -1
|
二、思路
动态规划的思路。组成 aim 所需的最小货币数，可以展开成分别组成 0 - aim 所需的最小货币数。我们申请一个二维数组 dp。列代表 0 - aim，行代表给的钱的面值。
dp 的第一列，此时 aim 为 0，那也就是说无需货币，即可组成 0 元。所以第一列全部填充 0
dp 的第一行，此时只能选择一个面值，也就是 arr[0]。那么此面值能组成的总钱数为 arr[0], 2*arr[0] ... k*arr[0]。当 k*arr[0] 等于某个 aim 时，填充 dp[ 0 ][ k*arr[0] ] 为 k。其他位置所代表的钱数一律找不开，所以一律设置为 正数的最大值。
dp 的其他位置 dp[i][j] 如何计算呢？j 代表目前的总钱数 aim，i 代表当前的面值 arr[i]。此时我们求 dp[i][j] ，有多种情况
- 如果不使用 i 位置的钱面值，那么就取
dp[i-1][j]。表示总钱数 j 没有变的情况下，不使用 i 位置的钱面值，这个位置是我们的 dp[i][j] 最小值的一个条件。
- 如果使用一张 i 位置的钱面值，那么就取
dp[i-1][j - arr[i]] + 1。我们使用一张 i 位置的钱面值，那么此时总钱数就要减去 arr[i]，那么我们已经求得了 dp[i][j - arr[i]] 的位置的最小值，直接拿来用
- 如果使用两张 i 位置的钱面值，那么就取
dp[i-1][j - 2*arr[i]] + 2。同上
- 如果使用 K 张 i 位置的钱面值，那么就取
dp[i-1][j - k*arr[i]] + k。同上
加深一下思路，行代表给定的钱的面值，列代表当前要组成的总钱数。好的，那么：
1
2
3
4
5
6
7
8
9
10
11
| dp[i][j] = min( dp[i-1][ j-k*arr[i] ] + k ) 此时 k >= 0 转换如下
dp[i][j] = min(dp[i-1][j], dp[i-1][ j-k*arr[i] ] + k ) 此时 k >= 1
dp[i][j] = min(dp[i-1][j], dp[i-1][ j-(y+1)*arr[i] ] + y+1) 使用 y+1 替换 k，此时 y >= 0
dp[i][j] = min(dp[i-1][j], dp[i-1][ j - y*arr[i] - arr[i] ] + y+1) 此时 y >= 0
由于表达式 dp[i-1][ j - y*arr[i] - arr[i] ] + y (y >= 0)，我们可以做出判断
min{ dp[i-1][ j - y*arr[i] - arr[i] ] + y } (y >= 0) 其中 y 表示使用了 y 张面值为 arr[i] 的钱。也就是说我们使用了 y 张面值为 arr[i] 的钱成功/不成功的让总钱数变为 aim。即有如下：
dp[i][ j - arr[i] ] = min{ dp[i-1][ j - y*arr[i] - arr[i] ] + y }, y >= 0
所以最终的表达式就变为了
dp[i][j] = min( dp[i-1][j], dp[i][ j-arr[i] ] + 1 )
|
注意，我们需要判断条件，上面表达式中也有不成功的让总数变为 aim 的情况。也就是 j - arr[i] < 0 的情况，就说明发生了越界。说明 arr[i] 太大了，用一张都会超过总钱数 j。如果不能成功让钱的总数变为想要的数字，那就填充 max 作为标志，最后再来判断 max 这个标志即可。
三、代码
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
| #include <vector>
#include <iostream>
class Solution {
public:
int min_coins(const std::vector<int>& arr, int aim) {
if (arr.empty() || aim < 0) {
return -1;
}
int n = arr.size();
int32_t max = INT32_MAX;
std::vector<std::vector<int>> dp(n, std::vector<int>(aim+1, 0));
for (int j = 1; j <= aim; ++j) {
dp[0][j] = max;
if (j - arr[0] >= 0 && dp[0][j-arr[0]] != max) {
dp[0][j] = dp[0][j-arr[0]] + 1;
}
}
int left = 0;
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= aim; ++j) {
left = max;
if (j - arr[i] >= 0 && dp[i][j-arr[i]] != max) {
left = dp[i][j-arr[i]] + 1;
}
dp[i][j] = std::min(left, dp[i-1][j]);
}
}
return dp[n-1][aim] != max ? dp[n-1][aim] : -1;
}
};
int main() {
Solution s;
std::vector<int> arr{5, 2, 5, 2};
auto res = s.min_coins(arr, 10);
std::cout << res << std::endl;
return 0;
}
|
时间复杂度和空间复杂度都为 O(n * aim)