这里介绍组合方案数的求法。
        给定N个正整数和M，用这N个数中的一些数进行求和，使得和为M，问方案数。该问题可以采用动态规划的方法快速求得。

        设dp(x，y)表示从序号为1~x的数中选使得和为y的方案数，则有状态转移方程:

        初始化dp(1，value(1))=1，其余全为0。答案即为dp(N，M)。
        可以把数组压缩至1维，从而得到时间复杂度O(NM)的算法。
        示例代码如下，这里对MOD取模:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>

using namespace std;
int op[10001];
int dp[10001] = {0};
const int MOD = static_cast<const int>(1e9 + 7);

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)cin >> op[i];
    dp[op[1]] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = M; j >= 0; j--) {
            if (j == op[i])dp[j] = (1 + dp[j]) % MOD;
            else if (j > op[i])dp[j] = (dp[j] + dp[j - op[i]]) % MOD;
        }
    }
    cout << dp[M];
    return 0;
}

        如果要求序号为x的数必须被选入，可以建立另一个数组dp2，储存从x~N的方案数，进行两遍DP。则含x的方案总数为:

        这样查询复杂度O(M)，注意这时数组不能压缩。