四种面值的货币：
$1, 5, 10, 25$

1,5,10,25，每种均有无数张可用，给定一个整数
$aim$

aim 表示要凑齐的金额，计算有多少种方法可以凑齐？

可以看出，上面的题目是一个完全背包问题，我们尝试用五种方法来对它进行求解，来体会不同方法的差异，了解动态规划的推导

暴力枚举

最简单的一种方法，用循环来枚举每种货币的数目。因为比较低效，当货币面值太多或者要凑齐的金额很大时，就不方便使用这种方法。

时间复杂度：
$O(aim^4)$

O(aim4)

#include <iostream> using namespace std; int v[] = {1, 5, 10, 25}; int main(void) { int res = 0, aim;  cin >> aim; for (int i = 0; i <= aim / v[0]; i++) for (int j = 0; j <= aim / v[1]; j++) for (int k = 0; k <= aim / v[2]; k++) for (int h = 0; h <= aim / v[3]; h++) if (i * v[0] + j * v[1] + k * v[2] + h * v[3] == aim)       res++;  cout << res << endl; return 0; } 

无返回值的深度优先搜索

暴力搜

1）如果能取到目标金额
$aim$

aim，就使全局变量
$res$

res 加
$1$

1 并返回

2）如果不能取到目标金额，就直接返回

3）否则就分两种情况：取当前面值货币
$v[u]$

v[u] 或跳入下一层
$u+1$

u+1，进行递归求解。

时间复杂度：
$O(aim^4)$

O(aim4)

#include <iostream> using namespace std; int v[] = {1, 5, 10, 25}; int res, aim; //u表示当前的层数，state表示当前凑到的金额 void dfs(int u, int state) { if (state == aim){   res++; return; } if (u == 4 || state > aim){ return; } //取当前面值货币  dfs(u, state + v[u]); //跳入下一层 dfs(u + 1, state); } int main(void) {  cin >> aim; dfs(0, 0);  cout << res << endl; return 0; } 

有返回值的深度优先搜索

每次利用一个
$res$

res 来存储当前的值

$begin{cases} res=1&state = aim\ res=0&u=4~||~state>aim\ res=dfs(u, state + v[u]) + dfs(u + 1, state)&其他 end{cases}$

⎩⎪⎨⎪⎧​res=1res=0res=dfs(u,state+v[u])+dfs(u+1,state)​state=aimu=4 ∣∣ state>aim其他​

1）如果能取到目标金额
$aim$

aim，局部变量
$res=1$

res=1 并返回

2）如果不能取到目标金额，局部变量
$res=0$

res=0 并返回

3）否则就拆分为两种情况：局部变量
$res=$

res= 取当前面值货币的方法数
$+$

+ 取下一面值货币的方法数，即
$dfs(u, state + v[u]) + dfs(u + 1, state)$

dfs(u,state+v[u])+dfs(u+1,state)，进行递归求解。

最后返回
$res$

res 即可。

时间复杂度：
$O(aim^4)$

O(aim4)

#include <iostream> using namespace std; int v[] = {1, 5, 10, 25}; int aim; //u表示当前的层数，state表示当前凑到的金额 int dfs(int u, int state) { int res = 0; if (state == aim){   res = 1; } else if (u == 4 || state > aim){   res = 0; } else{ //取当前面值货币的方法数 + 取下一面值货币的方法数   res = dfs(u, state + v[u]) + dfs(u + 1, state); } return res; } int main(void) {  cin >> aim;    cout << dfs(0, 0) << endl; return 0; } 

记忆化深度优先搜索

会发现每次在计算
$dfs(u, state)$

dfs(u,state) 时，会有很多次重复的计算，比如取了
$10$

10 张一元和
$0$

0 张五元时，此时需要计算
$dfs(2, 10)$

dfs(2,10)，之后取了
$5$

5 张一元和
$1$

1 张五元时需要再次计算
$dfs(2, 10)$

dfs(2,10)。

此时，可以用一个
$dp$

dp 矩阵来记录每种情况是否被计算过，用空间来换时间。

如果
$dfs(u, state)$

dfs(u,state) 没有被计算过，就进行计算并将数值记录在
$dp[u][state]$

dp[u][state] 中。如果被计算过，就直接使用
$dp[u][state]$

dp[u][state] 即可。

因为情况只有
$4*aim$

4∗aim 种，只需要计算
$4*aim$

4∗aim 次，所以时间复杂度可以优化到
$O(4*aim)$

O(4∗aim)

#include <iostream> using namespace std; int v[] = {1, 5, 10, 25}; int aim; int dp[5][1005]; int dfs(int u, int state) { //如果已经计算过，直接返回即可  if (dp[u][state] != 0){ return dp[u][state]; } int res = 0; if (state == aim){   res = 1; } else if (u == 4 || state > aim){   res = 0; } else{   res = dfs(u, state + v[u]) + dfs(u + 1, state); } return dp[u][state] = res; } int main(void) {  cin >> aim;    cout << dfs(0, 0) << endl; return 0; } 

动态规划

直接对
$dp$

dp矩阵进行操作，通过矩阵来进行状态转移

$dp[i][j]：表示使用前i种面值的货币来凑出金额j的方法数$

dp[i][j]：表示使用前i种面值的货币来凑出金额j的方法数

状态转移方程：

$dp[i+1][j]=begin{cases} dp[i][j]&j<v[i]\ dp[i][j]+dp[i+1][j-v[i]]&j≥v[i] end{cases}$

dp[i+1][j]={dp[i][j]dp[i][j]+dp[i+1][j−v[i]]​j<v[i]j≥v[i]​

1）如果
$j<v[i]$

j<v[i]，表示当前需要的金额
$j$

j 小于当前面值的货币
$v[i]$

v[i]，此时不能取当前面值货币，所以只能由
$dp[i][j]$

dp[i][j] 转移而来。

2）如果
$jgeq v[i]$

j≥v[i]，表示当前需要的金额
$j$

j 大于等于当前面值的货币
$v[i]$

v[i]，此时可以不取当前面值货币也可以取当前面值货币，所以可以由
$dp[i][j]$

dp[i][j] 和
$dp[i+1][j-v[i]]$

dp[i+1][j−v[i]] 转移而来。

矩阵的最后一个元素
$dp[4][aim]$

dp[4][aim]：表示用前
$4$

4 种货币来凑出金额
$j$

j ，就是最后的答案。

因为一共有
$4$

4 种货币，目标金额为
$j$

j ，所以
$dp$

dp 矩阵大小是
$4×aim$

4×aim。又因为求解过程就是求这个矩阵，所以时间复杂度为：
$O(4*aim)$

O(4∗aim)

#include <iostream> using namespace std; int v[] = {1, 5, 10, 25}; int aim; int dp[5][1005]; int main(void) {  cin >> aim;  dp[0][0] = 1; for (int i = 0; i < 4; i++){ for (int j = 0; j <= aim; j++){ if (j < v[i])     dp[i + 1][j] = dp[i][j]; else     dp[i + 1][j] = dp[i][j] + dp[i + 1][j - v[i]]; } }    cout << dp[4][aim] << endl; return 0; }