答案范围并不在int内，一定要使用long long!

思路： 经典的y式dp法

1.状态表示 f[i][j]: 表示从前i个数中选，总和刚好为j的方案，属性为Count。

2.状态计算 以 选择/不选择 第i个物品为划分， 1.当不选择第i个物品时: f[i][j] += f[i-1][j] 2.当选择第二个物品时: f[i][j] += f[i-1][j-v[i]]

切记我们这里f[i][j]中记录的是前i个数中总和为j的方案总数， 是在计算数量，也就是+=。

还有就是初始步骤，f[0][0]为1， 因为从前0个数中选总和为0也是一种方案。

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
int n, m;
int v[N], f[N], s[N][N];

//基础版二维
void base() {
    s[0][0] = 1;
    for (int i = 1; i<=n; i++) {
        for (int j = 0; j<=m; j++) {
            s[i][j] += s[i-1][j];
            if (j >= v[i]) s[i][j] += s[i-1][j-v[i]];
        }
    }
    cout << s[n][m];
}

//01背包优化，一维滚动数组
void op() {
    f[0] = 1;
    for (int i = 1; i<=n; i++) {
        for (int j = m; j>=0; j--) {
            f[j] += f[j-v[i]];
        }
    }
    cout << f[m];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i<=n; i++) cin >> v[i];

    // base();
    op();

    return 0;
}

将数字之和M看做背包容量

把每个数ai看做看做是体积为ai的物品

// 未优化代码
// 从前i个物品中选，且价值为0的方案数均为1
// 什么都不选就是一种选法
for (int i = 0; i < 110; i++)
    f[i][0] = 1;

for (int i = 1; i <= n; i++)
{
    int v;
    cin >> v;
    for (int j = 0; j <= m; j++)
    {
        // 不选当前物品
        f[i][j] = f[i - 1][j];
        // 选当前物品
        if (j >= v)// 选法为从前i - 1个数中选且价值为j - v的所有选法
            f[i][j] += f[i - 1][j - v];
    }
}

// 优化后代码
f[0] = 1;
for (int i = 0; i < n; i++)
{
    int v;
    cin >> v;
    for (int j = m; j >= v; j--)
        f[j] += f[j - v];
}

赵(hetao2863173)： 答案范围并不在int内，一定要使用long long!

hetao24883491：答案范围在int内，不要使用long long!

这两位大神不要再争了，我给大家揭秘：

真的要用long long!!!

试试这个👀️

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const long long N = 10010;
long long n, m;
long long v[N], f[N], s[N][N];
void base() {
    s[0][0] = 1;
    for (int i = 1; i<=n; i++) {
        for (int j = 0; j<=m; j++) {
            s[i][j] += s[i-1][j];
            if (j >= v[i]) s[i][j] += s[i-1][j-v[i]];
        }
    }
    cout << s[n][m];
}
void op() {
    f[0] = 1;
    for (int i = 1; i<=n; i++) {
        for (int j = m; j>=0; j--) {
            f[j] += f[j-v[i]];
        }
    }
    cout << f[m];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i<=n; i++) cin >> v[i];
    op();
    return 0;
}

答案范围在int内，不要使用long long!