給定一個(gè)數(shù)組稽穆，數(shù)組中為不同的數(shù)代表不同錢的面值冠王，同時(shí)給定一個(gè)需要兌換零錢的錢數(shù)，任意使用不同面值不同數(shù)量的錢來兌換舌镶，求一共有多少種方法
解法一：
- 思路：暴力遞歸
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;
}
解法二：
- 思路：記憶法版确，由于暴力遞歸中存在很多重復(fù)計(jì)算，所以記憶法使用一個(gè)二維數(shù)組去記錄遞歸的結(jié)果值乎折，避免了大量重復(fù)計(jì)算
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;
}
解法三：
- 思路：動(dòng)態(tài)規(guī)劃绒疗，記憶法只是簡(jiǎn)單地記錄了遞歸的結(jié)果集，動(dòng)態(tài)規(guī)劃去尋找了結(jié)果集的計(jì)算順序骂澄，找出關(guān)系吓蘑，利用遞推的公式去代替枚舉過程
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];
}
