多重集组合数

 //多重集组合数

        //有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();

        }

    }

    //有时候是求余数,在循环里取余,避免溢出,偶尔加上除数避免结果出现负数

}