一道斯特林数题，c++代码

Question

题目描述
给定n 个有标号的球，标号依次为1，2，…，n。将这n个球放入r 个相同的盒子里，不允许有空盒，问有多少种放置方法。
例如把4个球放入2个盒子有7种方法，这7 种不同的放置方法依次为：
{(1),(234)}, {(2),(134)},
{(3),(124)}, {(4),(123)},
{(12),(34)}, {(13),(24)},{(14),(23)}。

输入格式
第一行输入两个整数n,r(1<=r<=n<=20)。

输出格式
输出一个整数表示方案总数。

输入样例
4 2

输出样例
7

Answer 1

使用第二类斯特林数解

#include<cstdio>
long long a[25][25]; //a数组是用来递推的数组，注意本题需要使用longlong类型
int main()
{
    int r,n;
    scanf("%d %d",&n,&r); //输入球数以及盒子数
    for(int i=1;i<=n;i++) //外层循环枚举球数
    {
        for(int j=1;j<=r;j++) //内层循环枚举盒子数
        {
            if(i<j||j==0) break; 
            //如果盒子数大于球数，或者球数为0，就没有方法
            else if(i==1||j==1) a[i][j]=1; 
            //如果盒子数等于1或者球数等于1，就只有一种方法
                 else a[i][j]=a[i-1][j-1]+j*a[i-1][j]; 
                 //常规情况
        }
    }
    printf("%lld\n",a[n][r]); //输出解
    return 0;  //结束
}  

参考
https://blog.csdn.net/qq_42995099/article/details/82193829

补个扩展，LeetCode的第一类斯特林数题目
https://leetcode-cn.com/problems/determine-whether-matrix-can-be-obtained-by-rotation