作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序
题目链接：题目链接
题面：
小王顺利通过天桥后，进入到了太空奖励关卡。在小王眼前出现了无数多个小仙女，正和小王打着招呼，还向小王索要联系方式！
小王闭上眼睛想了想，自己可是有花之主，还是算了，于是准备扭头就走，但是小王突然想起，自己的朋友还都是单身，这是帮助自己朋友们脱单的好机会！
小王从兜里拿出 N 张不同的朋友名片，名片上写着自己朋友的姓名和联系方式，这正是面前小仙女们想要的。
小王可以将任意多张名片给一位或多位小仙女，小王认为给每位小仙女同一张名片是同一种选择，即将名片 X 给小仙女 A 和给小仙女 B 视为同一种方式。
这时小王想到一个问题，如果小王只有一张名片，小王可以将名片 1 交给任意一名小仙女，也就是只有一种方式。
如果小王有两张名片，小王可以将两张一起交给同一位小仙女，或者分开交给两位小仙女，也就是有两种方式。
如果小王有三张名片：
【1】小王可以分别将三张名片交给三位小仙女。
【2】或者名片 A、B 给仙女 1，名片 C 给仙女 2。
【3】或者名片 B、C 给仙女 1，名片 A 给仙女 2。
【4】名片 A、C 给仙女 1，名片 B 给仙女 2。
【5】或者三张名称全部给仙女 1；总计有 5 种方式。
那么请问小王如果有 N（0 < N < 2500）张不同名片，有几种给予方式？
知识点
- Java 二维数组基础使用
- 数组 DP 递推运算
初始代码
代码语言：javascript复制public class EMain {
public static Long doWork(int n) {
Long ans = 1L;
//代码编辑区 开始
//代码编辑区 结束
return ans;
}
public static void main(String[] args) {
//测试用例
System.out.printf((Objects.equals(2L,doWork(2)) ? "【√正确】" : "【X错误】") "不同名片数 %d,给予方式有%d种n",2,doWork(2));
System.out.printf((Objects.equals(5L,doWork(3)) ? "【√正确】" : "【X错误】") "不同名片数 %d,给予方式有%d种n",3,doWork(3));
}
样例说明
输入不同名片数 N，输出给予方式有几种。
如不同名片数 N = 2，则输出 2。
如不同名片数 N = 3，则输出 5
题解
考察第二斯特林数（贝尔数）的理解，也是一道动态规划递推题，需要打表处理。DP 公式为 Fn(i , j) = Fn(i - 1, j - 1) j * Fn(i - 1, j)，名片数为 N的发放情况种类数就等于 Fn(i , 0) Fn(i , 1) ... Fn(i , i - 1) Fn(i , i)。
参考代码如下：
代码语言：javascript复制import java.util.Objects;
public class EAns {
public static boolean INIT_FLAG = false;
public static Integer MAX_LENGTH = 2502;
public static Long MOD = 1314520L;
public static Long[][] ANS_TEMP;
public static Long[] ANS_LIST;
private static void init() {
ANS_TEMP = new Long[MAX_LENGTH][MAX_LENGTH];
ANS_LIST = new Long[MAX_LENGTH];
for(int i = 0; i < MAX_LENGTH; i ) {
for(int j = 0; j < MAX_LENGTH; j ) {
ANS_TEMP[i][j] = 0L;
}
ANS_TEMP[i][1] = 1L;
ANS_TEMP[i][i] = 1L;
ANS_LIST[i] = 0L;
}
for(int i = 2; i < MAX_LENGTH; i ) {
for(int j = 2; j <= i; j ) {
ANS_TEMP[i][j] = (ANS_TEMP[i - 1][j - 1] ANS_TEMP[i - 1][j] * j) % MOD;
}
}
for (int i = 1; i < MAX_LENGTH; i ) {
for (int j = 1; j <= i; j ) {
ANS_LIST[i] = (ANS_LIST[i] ANS_TEMP[i][j]) % MOD;
}
}
INIT_FLAG = true;
}
public static Long doWork(int n) {
Long ans = 1L;
//代码编辑区 开始
if(!INIT_FLAG) {
init();
}
ans = ANS_LIST[n];
//代码编辑区 结束
return ans;
}
public static void main(String[] args) {
//测试用例
System.out.printf((Objects.equals(2L,doWork(2)) ? "【√正确】" : "【X错误】") "不同名片数 %d,给予方式有%d种n",2,doWork(2));
System.out.printf((Objects.equals(5L,doWork(3)) ? "【√正确】" : "【X错误】") "不同名片数 %d,给予方式有%d种n",5,doWork(3));
}
}总结
要 AC 本题，必须学会 java 中 二位数组的基本用法，另外还要对动态规划和DP的算法有一定的了解，从而去递推第二斯特林数，最终通过本题。
