这里写目录标题

• 定义
• 思路
• 代码

定义

n = 3
m = 3
a={1,2,3}
M = 10000

不同的物品可以相互区分，同种物品区分不了
问从n中选择m个方案数
6{0+0+3,0+1+2,0+2+1,1+0+2,1+1+1,1+2+0}

思路

为了不重复记数，同一种类的物品最好一次性处理好。于是我们按照如下方式进行定义
dp[i+1][j]  从前i中物品中取出j个的组合总数
为了从前i种物品中取出j个，可以从第i个物品中取出k个，再从其他i-1物品取出j-k个
所以  dp[i+1][j]   =  (k=0,min ( j,a[i] ) )  ∑ dp [ i ] [ j - k ] 
直接计算这个递推关系的话复杂度是O(nm^2^)，不过因为我们有
(k=0,min(j,a[i])) ∑dp[i][j-k]= (k=0,min(j-1,a[i] )) ∑dp[i] [ j-1-k] +dp[i][j] -dp[i ][ j-1- ai] 
变形：dp[i+1][j] = dp[i+1][j-1] +dp[i][j] -dp[i][j-1-ai]     复杂度O(nm)

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1E2 + 7;
const int M = 1E3 + 7;
#define INF ~0ULL

int n, m;
int arr[N];
int dp[N][N];

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 - arr[i] >= 0)
                dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - arr[i]] + M) % M;
            else
                dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % M;
        }
    }
    cout << dp[n][m] << endl;
}

int main()
{
    n=3,m=3;
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    solve();
    system("pause");
}