如果暴力的深度优先:
class Solution {
// 定义硬币的面值数组
int fangx[4] = {25, 10, 5, 1};
// 计数变量,用于记录配合得到 n 的方法数
long long count = 0;
// 定义深度优先搜索函数
// now: 当前总值
// n: 目标总值
// notbig: 上一次选择的硬币面值索引
int dfs(int now, int n, int notbig) {
// 当前总值等于目标总值时,方法数加一
if (now == n) {
count += 1;
count %= 1000000007; // 防止计数过大,取模
return 0;
}
// 当前总值大于目标总值时,返回
if (now > n)
return 0;
// 遍历硬币面值数组,从上一次选择的硬币面值索引开始,防止重复计算
for (int i = notbig; i < 4; i++) {
// 递归调用深度优先搜索,更新当前总值为当前总值加上当前面值硬币的值
dfs(now + fangx[i], n, i);
}
return 0;
}
public:
// 定义计算配合得到 n 的方法数的函数
int waysToChange(int n) {
// 调用深度优先搜索函数
dfs(0, n, 0);
// 返回计数结果
return count;
}
};
但是很不幸,示例(28/30)无法完全通过,还是有点超时了。
那么我们考虑,不限各类硬币数,而且可以看作:面值25的硬币重量是25,价值也是25,这可以视为动态规划里面的完全背包问题,那么就简单了。
class Solution {
// 定义硬币的面值数组
int fangx[4] = {1, 5, 10, 25};
public:
// 计算配合得到 n 的方法数的函数
int waysToChange(int n) {
// 定义动态规划数组,长度为 n+1,初始化为0
vector<int> dp(n + 1, 0);
// 初始情况:当目标总值为0时,有一种方法,即不选取任何硬币
dp[0] = 1;
// 遍历硬币面值数组
for (int i = 0; i < 4; i++) {
// 遍历从当前硬币面值到目标总值的所有可能情况
for (int j = fangx[i]; j <= n; j++) {
// 更新动态规划数组中第 j 个元素的值
// 第 j 个元素的值等于第 j 个元素原有的值加上第 j-fangx[i] 个元素的值
// 即当前面值的硬币可以选择不同数量,对应不同情况下的配合方法数
dp[j] += dp[j - fangx[i]];
// 由于涉及大数运算,取模以避免溢出
dp[j] %= 1000000007;
}
}
// 返回配合得到目标总值 n 的方法数
return dp[n];
}
};