校招编程题---数字和为sum的方法数

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入描述:

输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
第二行为n个正整数Ai，以空格隔开。

输出描述:

输出所求的方案数

示例1

输入

5 15 5 5 10 2 3

输出

4

思路

动态规划算法。dp[i][j]表示前i个数字能够达到和为j的方法数。

然后是更新过程，首先有dp[i][j]=dp[i-1][j] （代表的是只用前面i-1个数就凑到j的方法数）。

之后是dp[i][j]+=dp[i-1][j-a[i]]; （表示的是加上前面i个数凑成j-a[i]的方法数，需要注意a[i] < j）

初始化时需要考虑到dp[0][0]=1，dp[0][j] = 0 ,之后的循环按照01背包的思路进行编写。

具体代码

#include <iostream>
using namespace std;
typedef long long LL;

int a[1234];
LL dp[1234][1234];
int n, sum;

void init() {
    for (int i = 0; i <= sum; i++){
        dp[0][i] = 0;
    }
    dp[0][0] = 1;
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n >> sum) {
        init();
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= a[i - 1]) dp[i][j] += dp[i - 1][j - a[i - 1]];
            }
        }
        cout << dp[n][sum] << endl;
    }
    return 0;
}