给定一个数组,数组中为不同的数代表不同钱的面值,同时给定一个需要兑换零钱的钱数,任意使用不同面值不同数量的钱来兑换,求一共有多少种方法

解法一:
  • 思路:暴力递归
1
2
3
4
5
6
7
8
9
10
11
int operation1(vector<int> A, int index, int aim) {
int result = 0;
if (index == A.size()) {
result = aim == 0 ? 1 : 0;
} else {
for (int i = 0; i * A[index] <= aim; i++) {
result += operation1(A, index + 1, aim - A[index] * i);
}
}
return result;
}
解法二:
  • 思路:记忆法,由于暴力递归中存在很多重复计算,所以记忆法使用一个二维数组去记录递归的结果值,避免了大量重复计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int operation2(vector<int> A, int index, int aim, vector<vector<int>> &map) {
int result = 0;
if (index == A.size()) {
result = aim == 0 ? 1 : 0;
} else {
int mapValue = 0;
for (int i = 0; i * A[index] <= aim; i++) {
mapValue = map[index + 1][aim - i * A[index]];
if (mapValue == -1) {
result += operation2(A, index + 1, aim - i * A[index], map);
} else {
result += mapValue;
}
}
}
map[index][aim] = result;
return result;
}
解法三:
  • 思路:动态规划,记忆法只是简单地记录了递归的结果集,动态规划去寻找了结果集的计算顺序,找出关系,利用递推的公式去代替枚举过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int operation3(vector<int> A, int aim, vector<vector<int>> &dp) {
// 初始化DP矩阵的第一列
for (int i = 0; i < A.size(); i++) {
dp[i][0] = 1;
}
// 初始化DP矩阵的第一行
for (int i = 0; i <= aim; i++) {
if (i % A[0] == 0) {
dp[0][i] = 1;
}
}
// DP过程
for (int i = 1; i < A.size(); i++) {
for (int j = 1; j <= aim; j++) {
if (j >= A[i]) {
dp[i][j] = dp[i - 1][j] + dp[i][j - A[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[A.size() - 1][aim];
}