计数组合型dp（四种小球盒子问题总结）-EW帮帮网

文章目录

计数组合型dp

计数组合型dp

本篇将结合两个题目从dp入手来解决

n个相同的小球放进k个相同的盒子，有几种分法

同时总结以下四种问题

n个相同的小球放进k个相同的盒子，有几种分法
n个相同的小球放进k个不同的盒子，有几种分法
n个不同的小球放进k个相同的盒子，有几种分法
n个不同的小球放进k个不同的盒子，有几种分法

看完此篇，直窥本质，再也不头疼小球盒子问题

P1025 数的划分

将数字n(<=200)分成k（<=6）部分,有几种分法，不考虑顺序。

本质即，n个相同的小球放进k个相同的盒子，不能为空，有几种分法

DFS

dfs传三个参数（上一个数字，选择数字总和，该选择第几个）

当选择k个后，满足sum=n，即ans++

int n,k,ans=0;
void dfs(int last,int sum,int c)
{
    if(c>k)
    {
        if(sum==n) ans++;
        return ;
    }
    for(int i=last;i*(k-c+1)<=n-sum;i++)
        dfs(i,sum+i,c+1);  
}
void solve()
{
    cin>>n>>k;
    dfs(1,0,1);
    cout<<ans<<"\n";
}

dp

要解决n个小球，放进k个盒子

同样的，由于盒子不能为空，所以先给每个盒子分配一个小球。

接下来只需考虑 $n - k$ 个小球怎么分配？

我们分类讨论 $n - k$ 个小球放在1或2或3…或k个盒子分别有几种情况
$dp[i][j]=\sum_{f=1}^{j}dp[i-j] [f]$

dp[i][j]表示 $i$ 个小球放在 $j$ 个盒子的方法数

那 $i - 1$ 个小球放进 $j - 1$ 个盒子应该如何表示呢？
$dp[i-1][j-1]=\sum_{f=1}^{j-1}dp[i-j] [f]$
将这两个式子拆分来看，易知：
$d p [i] [j] = d p [i - 1] [j - 1] + d p [i - j] [j]$
根据递推公式就可以写代码了

int dp[250][10];
void solve()
{
	int n,k;
	cin>>n>>k;
	dp[0][0]=1;
	fir(i,1,n)
	fir(j,1,k)
	{
		if(i>j)
		dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
		else dp[i][j]=dp[i-1][j-1];
	}
	cout<<dp[n][k]<<"\n";
}

还存在这样一种解释，将问题分成是否存在至少一个盒子里只有一个小球？

不存在：

现将k个盒子里放一个，剩下的n-k再分到k个盒子中
保证了每个盒子至少两个球

dp[i-j] [j]

存在：

第k个盒子只放一个球,剩下n-1个分给k-1个盒子

至少存在一个盒子有一个球

dp[i-1] [j-1]

在我看来这种解释有点牵强，不如上面有说服力。不过可以简单的理解，用来和下面这道“放苹果”做类比。

放苹果 - 计蒜客

本质，n个相同的小球放进k个相同的盒子，可以为空，有几种分法

下面以7个小球，3个盒子为例

请添加图片描述

在上面的题中，盒子不能为空，所以去考虑是否存在一个盒子只放了一个。

而本题可以为空，我们要考虑，是否存在一个盒子为空？

存在一个盒子为空:

dp[7] [3] = dp[7] [2]
那么有人要问了，如果存在两个盒子为空呢？

那自然需要接着向下分解，如图所示
dp[7] [2]本身就包括了有一个盒子为空的情况

不存在：

dp[7-3] [3]
那就先往每个盒子里放一个

上图展现的便是这样的分解过程，所以可得递推公式：
$d p [i] [j] = d p [i] [j - 1] + d p [i - j] [j]$

dp

#include<bits/stdc++.h>
 using namespace std;
 int t,m,n,f[15][15];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        f[0][0]=1;
        for(int i=0;i<=m;i++)
        { 
            for(int j=1;j<=n;j++)
            {
                if(j>i) f[i][j]=f[i][i];
                else
                f[i][j]=f[i][j-1]+f[i-j][j];
            }
        }
        cout<<f[m][n]<<'\n';
    }
}

递归

结合上图，从上向下递推。分解为叶子问题，返回1/0

#include<bits/stdc++.h>
 using namespace std;
 int t,m,n;
 int f(int x,int y)
 {
     if(x==1||y==1||x==0) return 1;
     if(x<0)  return  0;
     return f(x,y-1)+f(x-y,y);
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        cout<<f(m,n)<<'\n';
    }
}

总结

1. n个相同的小球放进k个相同的盒子，有几种分法

这两道题都是在讨论这种问题

前者不能为空，后者可以为空。

简单来说，只是递推的时候考虑是否有盒子只有一个小球还是考虑是否有盒子为空的区别

两者的递推公式分别为：
$d p [i] [j] = d p [i - 1] [j - 1] + d p [i - j] [j]$ 不为空

$d p [i] [j] = d p [i] [j - 1] + d p [i - j] [j]$ 为空

2. n个相同的小球放进k个不同的盒子，有几种分法

本质：a[i]+a[2]+a[3]+…+a[n]=k 的非负整数解数量

这就需要用隔板法，可以看这个两篇博客，有相关例题总结

D-小柒分糖果_牛客练习赛135（组合数，阶乘，逆元）-CSDN博客

河南萌新联赛2024第（四）场：河南理工大学 C 岗位分配 I 马拉松-CSDN博客

3. n个不同的小球放进k个相同的盒子，有几种分法

本质是，第二类斯特林数。

递推公式：
$d p [i] [j] = d p [i - 1] [j - 1] + d [i - 1] [j] * j$

斯特林数列是组合数学中的一个重要概念，分为两类：第一类斯特林数和第二类斯特林数。它们在计数问题中有着广泛的应用，特别是在排列、组合和分划等领域。
第一类斯特林数（通常记为 $s (n, k)$ 或 $S_1(n, k)$ ）表示将 $n$ 个不同元素划分为 $k$ 个非空循环排列的方式数。换句话说，它计数了将 $n$ 个元素进行圆排列，且恰好有 $k$ 个循环的方案数。
第二类斯特林数（通常记为 $S (n, k)$ 或 $S_2(n, k)$ ）则表示将 $n$ 个不同元素划分为 $k$ 个非空集合的方式数。这可以理解为将 $n$ 个元素放入 $k$ 个无标号的盒子中，且每个盒子至少有一个元素的不同放法数。
这两类斯特林数都满足一些有趣的递推关系和性质，并且与贝尔数、阶乘等组合数学中的其他重要概念有着密切的联系。
例如，第二类斯特林数的一个递推关系是：
$\cdot S(n-1, k) + S(n-1, k-1)$
这个递推关系可以这样理解：考虑第 $n$ 个元素，它要么单独形成一个集合（这种情况下，剩下的 $n - 1$ 个元素需要划分为 $k - 1$ 个集合），要么被添加到已有的 $k$ 个集合中的任意一个（这种情况下，剩下的 $n - 1$ 个元素已经划分为 $k$ 个集合）。
斯特林数列在计算机科学、概率论、统计学等多个领域都有应用，是组合数学中一个非常基础和重要的工具。

4.n个不同的小球放进k个不同的盒子，有几种分法

$n^k$

题外话

从周四便开始着手，现在也算整理了个皮毛。意义何在？我也说不清楚

姑且算作，兴趣使然。

虽然没能去接触数学竞赛，现在巧然打算法，也算一种安慰补偿，以另一种方式的回馈

如此，忍痛言，无复憾矣

悟已往之不谏，知来者之可追。实迷途之未远，觉今是而昨非

计数组合型dp（四种小球盒子问题总结）

文章目录