资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

计数组合型DP：四种小球盒子问题总结

创作时间:

作者:

@小白创作中心

计数组合型DP：四种小球盒子问题总结

引用

CSDN

https://blog.csdn.net/2301_81692739/article/details/146437896

本文将深入探讨计数组合型动态规划（DP）问题，特别是关于小球放入盒子的四种不同情况。通过两个具体题目，文章详细介绍了DFS和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-kn−k个小球怎么分配？

我们分类讨论n − k n-kn−k个小球放在1或2或3…或k个盒子分别有几种情况

d p [ i ] [ j ] = ∑ f = 1 j d p [ i − j ] [ f ] dp[i][j]=\sum_{f=1}^{j}dp[i-j] [f]dp[i][j]=f=1∑j dp[i−j][f]

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

那i − 1 i-1i−1个小球放进j − 1 j-1j−1个盒子应该如何表示呢？

d p [ i − 1 ] [ j − 1 ] = ∑ f = 1 j − 1 d p [ i − j ] [ f ] dp[i-1][j-1]=\sum_{f=1}^{j-1}dp[i-j] [f]dp[i−1][j−1]=f=1∑j−1 dp[i−j][f]

将这两个式子拆分来看，易知：

d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − j ] [ j ] dp[i][j]=dp[i-1][j-1]+dp[i-j][j]dp[i][j]=dp[i−1][j−1]+dp[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[i][j]=dp[i][j-1]+dp[i-j][j]dp[i][j]=dp[i][j−1]+dp[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 ] dp[i][j]=dp[i-1][j-1]+dp[i-j][j]dp[i][j]=dp[i−1][j−1]+dp[i−j][j]不为空

d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + d p [ i − j ] [ j ] dp[i][j]=dp[i][j-1]+dp[i-j][j]dp[i][j]=dp[i][j−1]+dp[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 dp[i][j]=dp[i-1][j-1]+d[i-1][j]*jdp[i][j]=dp[i−1][j−1]+d[i−1][j]∗j

斯特林数列是组合数学中的一个重要概念，分为两类：第一类斯特林数和第二类斯特林数。它们在计数问题中有着广泛的应用，特别是在排列、组合和分划等领域。

第一类斯特林数（通常记为s ( n , k ) s(n, k)s(n,k)或S 1 ( n , k ) S_1(n, k)S1 (n,k)）表示将n nn个不同元素划分为k kk个非空循环排列的方式数。换句话说，它计数了将n nn个元素进行圆排列，且恰好有k kk个循环的方案数。

第二类斯特林数（通常记为S ( n , k ) S(n, k)S(n,k)或S 2 ( n , k ) S_2(n, k)S2 (n,k)）则表示将n nn个不同元素划分为k kk个非空集合的方式数。这可以理解为将n nn个元素放入k kk个无标号的盒子中，且每个盒子至少有一个元素的不同放法数。

这两类斯特林数都满足一些有趣的递推关系和性质，并且与贝尔数、阶乘等组合数学中的其他重要概念有着密切的联系。

例如，第二类斯特林数的一个递推关系是：

S ( n , k ) = k ⋅ S ( n − 1 , k ) + S ( n − 1 , k − 1 ) S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)S(n,k)=k⋅S(n−1,k)+S(n−1,k−1)

这个递推关系可以这样理解：考虑第n nn个元素，它要么单独形成一个集合（这种情况下，剩下的n − 1 n-1n−1个元素需要划分为k − 1 k-1k−1个集合），要么被添加到已有的k kk个集合中的任意一个（这种情况下，剩下的n − 1 n-1n−1个元素已经划分为k kk个集合）。

斯特林数列在计算机科学、概率论、统计学等多个领域都有应用，是组合数学中一个非常基础和重要的工具。