算法

(DP,01背包问题) $O(nm)$

可以转化为0-1背包问题求方案数：

• 将总和 $M$看作背包容量；
• 将每个数 $A_i$ 看作体积为 $A_i$ 的物品；

时间复杂度

背包问题的时间复杂度是 O(nm)O(nm)。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int f[N];

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