文字教学

这是一道01背包方案数问题，核心是统计刚好花完M元的点菜方法数。

1. 状态定义：设 dp[j] 表示刚好花 j 元的方案数。
2. 初始状态：dp[0] = 1，因为花0元只有一种方法（什么都不点）。
3. 状态转移：对于每个菜的价格 a_i，从后往前遍历 j（避免重复选同一个菜）：
   • 若 j >= a_i，则 dp[j] += dp[j - a_i]（之前花 j-a_i 元的方案，加上这个菜就变成花 j 元的方案）。
4. 最终答案：dp[M] 就是刚好花完M元的方案数。

代码

#include <bits/stdc++.h>
using namespace std;

int dp[10005];
int a[105];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= a[i]; --j) {
            dp[j] += dp[j - a[i]];
        }
    }
    cout << dp[m] << endl;
    return 0;
}