题目（DP）

代码

为了不重复计数，同一种类的物品最好一次性处理好。
dp[i+1][j] := 从前i种物品中取出j个的组合总数 O(nm²)
从前i种物品种取出j个，可以先从前i-1种物品中取出j-k个，再从第i种物品种取出k个添加进来

O(nm)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MAX_N = 1000; 
const int MAX_M = 1000;
int dp[MAX_M+1][MAX_N+1]; // DP数组 //输入 
int n = 3;   
int m = 3;
int a[3] = {1, 2, 3};
int M = 10000;void solve(){// 一个都不取的方法总是只有一种for(int i = 0 ; i <= n ; i ++)dp[i][0] = 1;for(int i = 0 ; i < n ; i ++)for(int j = 1 ; j <= m ; j ++){if(j-1-a[i] >= 0) // 在有取余的情况下，避免减法运算的结果出现负数 dp[i+1][j] = (dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]] + M) % M;elsedp[i+1][j] = (dp[i+1][j-1] + dp[i][j]) % M;}printf("%d\n", dp[n][m]);					 
} 	int main(){	solve(); return 0;
}