Cpp 算法题：集合组合方案数计算 (限制条件)

解题思路：

首先，我们可以将问题转化为一个集合的问题，即从1到N中选取一些数，组成一个集合。 然后，我们可以通过动态规划来解决该问题。 定义一个二维数组dp，其中dp[i][j]表示从1到i中选取数，且集合中包含j个数的方案数。 初始情况下，dp[i][0]=1，表示从1到i中不选取任何数的方案数为1。 然后，我们考虑每个数i是否选取进集合中。 如果不选取数i，那么方案数就等于dp[i-1][j]。 如果选取数i，那么方案数就等于dp[i-1][j-1]，但是需要排除掉与数i有限制的数。 因此，我们需要遍历所有的限制，如果限制中的某个数与数i相等，那么该方案数就需要减去dp[i-1][j-1]。 最后，我们将所有的方案数相加就可以得到结果。

具体实现：

首先，我们读入N和M。 然后，我们定义一个二维数组restrictions，用来存储限制的关系。 接下来，我们定义一个二维数组dp，大小为(N+1)×(N+1)，并初始化dp[i][0]=1。 然后，我们遍历1到N的每个数i，对于每个数i，我们遍历1到N的每个数j，计算dp[i][j]，并根据限制更新dp[i][j]。 最后，我们输出dp[N][j]的和，即为结果。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> restrictions(M, vector<int>(2));
    for (int i = 0; i < M; i++) {
        cin >> restrictions[i][0] >> restrictions[i][1];
    }
    
    vector<vector<int>> dp(N+1, vector<int>(N+1, 0));
    for (int i = 0; i <= N; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            for (int k = 0; k < M; k++) {
                if (restrictions[k][0] == i && restrictions[k][1] == j) {
                    dp[i][j] -= dp[i-1][j-1];
                    break;
                }
            }
        }
    }
    
    int result = 0;
    for (int j = 0; j <= N; j++) {
        result += dp[N][j];
    }
    
    cout << result << endl;
    
    return 0;
}