求大家帮我解答一下这道动态规划题

Question

现在有n种牌，第i种有ai张牌。

现在要出m张牌，可以从手牌里任意选择。出牌时同一种牌需要放在一起，且不同种类的牌需要按牌的种类编号从小到大摆放。

想知道一共有多少种出牌方式。对答案膜10^6 + 7的结果

想了很久还是不会

Answer 1

一个标准的多重背包问题，

#include <bits/stdc++.h>
using namespace std;
int n,m;//n种牌，出m张,根据n、m的大小开二维数组d[n+1][m+1] 
//这里假设n小于100，m小于1000 
int a[100],d[100][1000],s;//d[i][j]表示前i种牌出m张，一共多少种 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]; 
    d[0][0]=1;
    for(int i=1;i<=n;i++){
        d[i][0]=1;
        s+=a[i];//前i种牌一共s张 
        for(int j=1;j<=min(m,s);j++){//凑j张牌  //降维的话，这需要倒着做，参考01背包
            for(int k=0;k<=min(a[i],j);k++){//取k张i ，这是一个多重背包 
                d[i][j]+=d[i-1][j-k];
                d[i][j]%=1e6+7;
            } 
        }
    } 
    cout<<d[n][m]; //降维的话，倒着做。 
    return 0;
}