多重集组合数dp

经典dp：多重集组合数

多重集组合数问题

  • 一个有关计数的动态规划问题，含有优化的数学推导过程，蛮有意思的，就是太巧妙了，蒟蒻的自己肯定想不到，记录下。

问题描述

  • 有$n$种物品，第$i$种物品有$a_i$个，不同种类的物品可以相互区分，但相同种类的物品无法区分。现在从这些物品中取出$m$个，有多少种取法？答案需要模M。

    Sample Input

    1
    2
    3 3
    1 2 3

    Sample Output

    1
    6

    样例解释：

    有n=3种物品, 每种a={1,2,3}个, 取出m=3个, 取法result=6(0+0+3, 0+1+2, 0+2+1, 1+0+2, 1+1+1, 1+2+0).

思路&解法

很容易想到状态$dp[i][j]$表示前$i$种物品取$j$个的方法总数，状态转移方程为：

意思是：先从前$i-1$种物品中取$j-k$个，再从第$i$种物品种取$k$个，因此方法总数就是先从前$i-1$种物品中取$j-k$个的方法总数，这里需要注意$k$的上界是$j$和$a[i]$两者中的较小者（既要保证$j-k>0$，也要保证合法）。

时间复杂度为：$O(nm^2)$，可以开始搞了。

AC代码（$O(nm^2)$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005];
int dp[10005][10005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0]=1; //初始状态置1
		for(int j=1;j<=m;j++){
			int minx = min(j,a[i]);
			for(int k=0;k<=minx;k++) dp[i][j]+=dp[i-1][j-k];
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

优化

发现这个时间复杂度不是很给力，看看能不能再做点优化？

考虑状态转移方程：

将其右边展开，分类讨论：

  1. $j\leq a\left[i\right]$时：显然，括号内就是合并两式，得到：
  1. $j>a\left[i\right]$时：

于是，仿照1中的格式，写出一个类似的式子如下，方便合并：

我们把它展开：

发现等号右边多了一个$dp[i-1][j-a[i]-1]$，所以在合并的时候，需要在等号右边减掉，得出最终的状态转移方程如下：

可以用$O(nm)$的时间复杂度搞它。

AC代码（$O(nm)$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005];
int dp[10005][10005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0]=1;
		for(int j=1;j<=m;j++){
			if(j<=a[i]) dp[i][j]=dp[i-1][j]+dp[i][j-1];
			else dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1-a[i]];
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}
  • 此题为我们提供了一条优化$dp$方程的思路，即通过对方程求和式的展开进一步探索其与之前状态的联系，从而优化了时间复杂度，值得借鉴。