题目链接：题目链接
题面：
小王顺利通过天桥后，进入到了太空奖励关卡。在小王眼前出现了无数多个小仙女，正和小王打着招呼，还向小王索要联系方式！
小王闭上眼睛想了想，自己可是有花之主，还是算了，于是准备扭头就走，但是小王突然想起，自己的朋友还都是单身，这是帮助自己朋友们脱单的好机会！
小王从兜里拿出 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 递推运算
初始代码
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)。
参考代码如下：
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的算法有一定的了解，从而去递推第二斯特林数，最终通过本题。
