多重集组合数 dp

#include <cstdio>
#include <iostream>
using namespace std;
int n,m;
int a[1005];

int dp[1005][1005];


int main()
{
	while(cin >> n >> m){
		for(int i = 0;i < n;i++){
			cin >> a[i];
		}
		int M;
		
		cin >> M;
		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][j] + dp[i+1][j-1] - dp[i][j-1-a[i]] +M)%M; //谁能帮我看下这是为什么？？？
				else{
					dp[i+1][j] = dp[i][j] + dp[i+1][j-1]; 
				}
			}
		} 
	printf("%d\n",dp[n][m]);
	} 	
	return 0;
	
}

多重集组合数 dp

原文：http://blog.csdn.net/qq_24667639/article/details/45255455