//多重集组合数
//有n种物品,第i种物品有a[i]个,从这些物品中取出m个,有多少种取法
//dp[i+1][j]=取法个数,i-1为物品种数,j为取出个数。从第i种取出j个的取法个数
// 从前i-1种取出j个的取法(不包含第i种物品)和从前i种物品中包含第i种物品的取出j个的取法=dp[i+1][j]
//包含第i种物品的取出j个的取法,第i种至少一个,至多a[i]个。从i种物品中取出j-1个,第j个视为在第i种物品中
//这取出j-1个可以有0到a[i]-1个物品在第i种物品中,这样就是包含第i种物品的取出j个的取法个数
//但是取出j-1个中也可以有a[i]个物品在第i种物品中,这样就与a[i]-1个物品在第i种物品中的情况重复了,前提是a[i]<=j-1
//所以要减去第i种取a[i]个的取法即dp[i][j-1-a[i]]前i-1种取j-1-a[i]个,若a[i]>j-1,就不存在重复的问题
//所以递推关系式为dp[i+1][j]= dp[i][j]+dp[i+1][j-1]-dp[i][j-1-a[i]],
static void Main()
{
int m = int.Parse(Console.ReadLine());
int n = int.Parse(Console.ReadLine());
int[] a = { 1, 2, 3 };
int [,]dp = new int[1000, 1000];
for(int i=0;i<=m;i++)
for(int j=0;j<=n;j++)
{
dp[i, j] = 0;
}
for (int i = 0; i <= m; i++)
dp[i,0] = 1;
for (int i=0;i<m;i++)
for(int j=1;j<=n;j++)
{
if(j-1-a[i]>=0)
{
dp[i + 1, j] = (dp[i, j] + dp[i + 1, j - 1] - dp[i, j - a[i] - 1]);
}
else
{
dp[i + 1, j] = (dp[i, j] + dp[i + 1, j - 1]);
}
}
Console.WriteLine(dp[3, 3]);
Console.Read();
}
}
//有时候是求余数,在循环里取余,避免溢出,偶尔加上除数避免结果出现负数
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。