【题目来源】
洛谷：P1164 小A点菜 - 洛谷 (luogu.com.cn)
【题目描述】
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
不过 uim 由于买了一些书，口袋里只剩 \(M\) 元 \((M\le 10000)\)。
餐馆虽低端，但是菜品种类不少，有 \(N\) 种 \((N\le 100)\)，第 \(i\) 种卖 \(a_i\) 元 \((a_i\le 1000)\)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 \(1\) 秒。
【输入】
第一行是两个数字，表示 \(N\) 和 \(M\)。
第二行起 \(N\) 个正数 \(a_i\)（可以有相同的数字，每个数字均在 \(1000\) 以内）。
【输出】
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
【输入样例】
4 4
1 1 2 2
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1164 小A点菜》 #动态规划,dp# #搜索# #背包# #洛谷原创#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, m; // n-物品数量，m-目标和
int a[105]; // 存储每个物品的数值
int f[105][10005]; // DP数组，f[i][j]表示前i个物品组成j的方案数int main()
{// 输入物品数量和目标和cin >> n >> m;// 输入每个物品的数值for (int i = 1; i <= n; i++) cin >> a[i];// 动态规划求解for (int i = 1; i <= n; i++) // 遍历每个物品{for (int j = 1; j <= m; j++) // 遍历每个可能的和{if (a[i] == j) // 情况1：当前物品值正好等于目标和f[i][j] = f[i-1][j] + 1; // 方案数=不选它的方案数+只选它的方案(1种)else if (a[i] > j) // 情况2：当前物品值大于目标和f[i][j] = f[i-1][j]; // 不能选它，方案数等于前i-1个物品的方案数else // 情况3：当前物品值小于目标和f[i][j] = f[i-1][j] + f[i-1][j-a[i]]; // 方案数=不选它的方案数+选它的方案数}}// 输出前n个物品组成m的方案数cout << f[n][m];return 0;
}
// 使用记忆化DFS再写一遍
#include <bits/stdc++.h>
using namespace std;int n, m; // n-物品数量，m-目标和
int a[105]; // 存储每个物品的数值
int used[105]; // 标记物品是否被使用
int dp[105][10005]; // 记忆化数组，dp[step][s]表示从step开始选，当前和为s的方案数// 记忆化DFS函数
int dfs(int step, int s)
{int ans = 0;// 边界条件1：当前和超过目标值if (s > m) return 0;// 记忆化：如果已经计算过，直接返回结果if (dp[step][s]) return dp[step][s];// 边界条件2：已经考虑完所有物品if (step == n) {if (s == m) return 1; // 找到一种方案return 0;}// 选择当前物品used[step] = 1;ans += dfs(step + 1, s + a[step]);used[step] = 0;// 不选择当前物品ans += dfs(step + 1, s);// 存储计算结果return dp[step][s] = ans;
}int main()
{// 输入物品数量和目标和cin >> n >> m;// 输入每个物品的数值for (int i = 0; i < n; i++) cin >> a[i];// 初始化记忆化数组（全局变量自动初始化为0）memset(dp, 0, sizeof(dp));memset(used, 0, sizeof(used));// 从第0个物品开始，当前和为0cout << dfs(0, 0);return 0;
}
【运行结果】
4 4
1 1 2 2
3