滴滴出行2017秋招笔试真题-编程题汇总 [编程题]数字和为sum的方法数

题目链接：  [编程题]数字和为sum的方法数

题意：

   就下标不同就是不相同的一组，判断有多少组能组成 sum

刚开始用的dfs搜索，然后一直超时，改用动态规划，可以记忆化搜索（动态规划，有点难）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, sum;
    cin >> n >> sum;
    vector<int> a(n);
    vector<ll> dp(sum+1, 0);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = sum; j >= a[i]; j--) {
            dp[j] += dp[j-a[i]];
        }
    }
    cout << dp[sum] << endl;
    return 0;
}