0. 前言
PS：本人并不是集训队的成员，因此代码写的烂轻点喷。。。本专题一方面是巩固自己的算法知识，另一方面是给NBU学弟学妹们参考解题思路（切勿直接搬运抄袭提交作业！！！）最后，该系列博客AC代码均以Java语言提交，C/C++的可以参考思路编写代码
1. 题目详情
1.1 题目一：装错信封
1.1.1 题目信息
题目描述：
组合学中有这样一个问题：某人给五个朋友写信，邀请他们来家中聚会。请柬和信封交由助手去处理。粗心的助手却把请柬全装错了信封。请问：助手会有多少种装错的可能呢？
这个问题是是由当时有名的数学家约翰·伯努利(Johann Bernoulli，1667—1748)的儿子
丹尼尔·伯努利(Danid Bernoulli，17OO一1782)提出来的。
输入要求：
输入数据包含多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=10），n表示朋友的人数。
输出要求：
对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。
输入样例：
6
输出样例：
265
来源：
NBUOJ
1.1.2 算法思路（递推=>动态规划）
动态规划五步走（重要）：
- 状态定义：这一步是相当重要的，定义一个合适的状态表示是解题的关键，我们假设
dp[i]为前i个朋友全部装错信封的数量 - 状态转移方程：假设我们使用上一步骤的状态表示，那么我们需要思考 dp[i] 可以由哪些状态转移得到，我们推导得出公式为：dp[i] = (n - 1) * (dp[i - 1] + dp[i - 2]) 其中i >= 3`（稍后会进行证明）
- 状态初始化：由于我们在i<3时直接套用该公式会造成数组越界，因此我们需要初始化dp[1]、dp[2]的值
- 填表顺序：根据我们的状态转移方程，我们发现dp[i]的值可以由前两项推出，因此填表顺序是从左往右填写的
- 返回值：根据题目含义我们需要输出n个朋友全部装错信封的种数，因此我们填表完毕后需要返回的就是dp[n]
示例：我们假设输入为4进行画图举例：
前提：我们需要保证第4个朋友的信封不交给第四个朋友，因此可以选择给前3个朋友中任意一个，因此总数一定是需要 乘以 3（即n - 1）的
此时假设选择将Mail4交给friendx(1 <= x <= 3)，又可以分为两种情况：
- 信封Mailx交给了Friend4：
此时剩余2（即n - 2）位朋友的错误数为已知解dp[2]（即dp[n - 2]）
- 信封Mailx没有交给Friend4：
此时只要将剩余的n - 1个信封交给剩余n - 1个朋友即可，其中可以看做Friendx的位置替换为Friend4，此时错误种数为dp[3]（即dp[n - 1]）
因此最后得出公式：dp[i] = (n - 1) * (dp[i - 1] + dp[i - 2]) 其中i >= 3
1.1.3 AC代码（Java实现）
NBUOJ上面Java带中文注释会报错！因此这里放了两个版本的代码，前面不带注释的可以直接跑OJ通过，后面的方便读者阅读
1.1.3.1 不带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dp = new int[n + 1];
dp[1] = 0;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
System.out.println(dp[n]);
}
}
1.1.3.2 带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 朋友数目
// 1. 定义状态: dp[i]表示i个朋友装错信封的方案数
int[] dp = new int[n + 1];
// 2. 初始化
dp[1] = 0;
dp[2] = 1;
// 3. 状态转移
for (int i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
// 4. 返回值
System.out.println(dp[n]);
}
}
1.2 题目二：双色Hanoi塔
1.2.1 题目信息
题目描述：
设A、B、C是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则(1)：每次只能移动1 个圆盘；
规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则(3)：任何时刻都不允许将同色圆盘叠在一起；
规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。
试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样顺序叠置。
输入要求：
给定的正整数n
输出要求：
将计算出的最优移动方案输出。文件的每一行由一个正整数k和2个字符c1和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。
输入样例：
3
输出样例：
来源：
NBUOJ
1.2.2 算法思路（递归）
可以参考我之前写的博客：http://t.csdnimg.cn/XOjzm
这里不再赘述！
1.2.3 AC代码（Java实现）
NBUOJ上面Java带中文注释会报错！因此这里放了两个版本的代码，前面不带注释的可以直接跑OJ通过，后面的方便读者阅读
1.2.3.1 不带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dfs('A', 'B', 'C', n);
}
private static void move(char src, char dest, int n) {
System.out.println(n + " " + src + " " + dest);
}
private static void dfs(char src, char dest, char tmp, int n) {
if (n == 1) {
move(src, dest, 1);
} else {
dfs(src, tmp, dest, n - 1);
move(src, dest, n);
dfs(tmp, dest, src, n - 1);
}
}
}
1.2.3.2 带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 将n个盘子从'A'移动到'B'借助'C'
dfs('A', 'B', 'C', n);
}
/**
* 将n号盘子从src移动到dest
* @param src 原位置
* @param dest 目标位置
* @param n 盘子编号
*/
private static void move(char src, char dest, int n) {
// 打印移动轨迹
System.out.println(n + " " + src + " " + dest);
}
/**
* 将盘子1-n从src借助辅助柱子tmp移动到dest柱子
* @param src 原柱子
* @param dest 目标柱子
* @param tmp 辅助柱子
* @param n 盘子个数
*/
private static void dfs(char src, char dest, char tmp, int n) {
if (n == 1) {
// 只有一个盘子
move(src, dest, 1);
} else {
// 有多个盘子
// 1. 先移动前n - 1个盘子从src到tmp借助dest
dfs(src, tmp, dest, n - 1);
// 2. 然后将n号盘子从src移动到dest
move(src, dest, n);
// 3. 然后将前n - 1个盘子从tmp移动到dest借助src
dfs(tmp, dest, src, n - 1);
}
}
}
1.3 题目三：日程安排
1.3.1 题目信息
题目描述：
设有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次；
(2)每个选手一天只能参赛一次；
(3)循环赛在n-1天内结束。
输入要求：
整数k；k<=5。
输出要求：
一个n*n的日程安排表，其中n=2^k。
输入样例：
3
输出样例：
来源：
NBUOJ
1.3.2 算法思路（暴力求解）
这里直接给大家介绍我的算法思路了：直接观察输出测试用例我们可以发现本题类似于N皇后问题，只要求 横竖不能出现重复元素 ，再次观察输入数据量 k <= 5 所以矩阵最大尺寸就是 32 * 32完全可以暴力求解
本题建议直接看代码
算法步骤：
- 三层for循环，对于每一个位置遍历1-8数字，只要保证不与当前行元素以及当前列元素重复即可
1.3.3 AC代码（Java实现）
NBUOJ上面Java带中文注释会报错！因此这里放了两个版本的代码，前面不带注释的可以直接跑OJ通过，后面的方便读者阅读
1.3.3.1 不带注释版本
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = (int) Math.pow(2, k);
int[][] matrix = new int[n][n];
List<Set<Integer>> rowSet = new ArrayList<>();
List<Set<Integer>> colSet = new ArrayList<>();
for (int i = 0; i < n; i++) {
rowSet.add(new HashSet<>());
colSet.add(new HashSet<>());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int target = 1; target <= n; target++) {
if (!rowSet.get(i).contains(target) && !colSet.get(j).contains(target)) {
matrix[i][j] = target;
rowSet.get(i).add(target);
colSet.get(j).add(target);
break;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println(matrix[i][n - 1]);
}
}
}
1.3.3.2 带注释版本
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = (int) Math.pow(2, k); // 比赛人数
// 日程表
int[][] matrix = new int[n][n];
// rowSet，保存任意一行的已存放元素
List<Set<Integer>> rowSet = new ArrayList<>();
// colSet，保存任意一列的已存放元素
List<Set<Integer>> colSet = new ArrayList<>();
for (int i = 0; i < n; i++) {
rowSet.add(new HashSet<>());
colSet.add(new HashSet<>());
}
// 暴力求解
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 枚举1-n
for (int target = 1; target <= n; target++) {
if (!rowSet.get(i).contains(target) && !colSet.get(j).contains(target)) {
// 当前行、列都没有出现过
matrix[i][j] = target;
rowSet.get(i).add(target);
colSet.get(j).add(target);
break;
}
}
}
}
// 打印结果
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println(matrix[i][n - 1]);
}
}
}
1.3.4 扩展题
这里放一些跟本题类似的OJ题（读者可自行尝试解题）：
- NowCoder N皇后问题：https://www.nowcoder.com/profile/277484796/codeBookDetail?submissionId=434759618
1.4 题目四：小明的烦恼
1.4.1 题目信息
题目描述：
小明最近新买了一个房间，为了给它做装修，想要给它铺上地砖。然而现有的地砖只有两种规格分别为1米1米、2米2米，由于小明买的房间有点小，宽度只有3米，长度为N米。当然这样一个房间也足够他自己一个人住了。那么如果要给这个房间铺设地砖，且只用以上这两种规格的地砖，请问有几种铺设方案。
输入要求：
输入的第一行是一个正整数C，表示有C组测试数据。接下来C行，每行输入一个正整数n（1<=n<=30），表示房间的长度。
输出要求：
对于每组输入，请输出铺设地砖的方案数目。
输入样例：
2
2
3
输出样例：
3
5
来源：
NBUOJ
1.4.2 算法思路（递推=>动态规划）
本题与【NBUOJ刷题笔记】递推/递归+分治策略1中的铺砖很类似
动态规划五步走（重要）：
- 状态定义：这一步是相当重要的，定义一个合适的状态表示是解题的关键，我们假设
dp[i]表示为宽度为3，长度为i的铺设方案 - 状态转移方程：假设我们使用上一步骤的状态表示，那么我们需要思考 dp[i] 可以由哪些状态转移得到，我们可以根据最后部分砖的铺设方案进行划分，因此可以得出状态转移方程为：
dp[i] = dp[i - 1] + 2 * dp[i - 2](其中i >= 3) - 状态初始化：由于我们在i<3时直接套用该公式会造成数组越界，因此我们需要初始化dp[1]、dp[2]的值
- 填表顺序：根据我们的状态转移方程，我们发现dp[i]的值可以由前两项推出，因此填表顺序是从左往右填写的
- 返回值：根据题目含义我们需要输出长度为n的铺设方案数，因此我们填表完毕后需要返回的就是dp[n]
示例：也许上面的文字描述有点抽象，还是以画图进行举例：假设我们需要求取dp[i]即宽度为3，长度为i的铺设方案数
相信此图一出，犹如醍醐灌顶！状态转移方程也就显而易见了：dp[i] = dp[i - 1] + 2 * dp[i - 2](其中i >= 3)
1.4.3 AC代码（Java实现）
NBUOJ上面Java带中文注释会报错！因此这里放了两个版本的代码，前面不带注释的可以直接跑OJ通过，后面的方便读者阅读
1.4.3.1 不带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
while (count > 0) {
int n = scanner.nextInt();
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 3;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + 2 * dp[i - 2];
}
System.out.println(dp[n]);
count--;
}
}
}
1.4.3.2 带注释版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt(); // 读取测试数据组数
while (count > 0) {
int n = scanner.nextInt(); // 读取每一组测试用例
// 1. 状态定义：dp[i]表示宽度为3，长度为i的铺设方案数
int[] dp = new int[n + 1];
// 2. 状态初始化
dp[1] = 1;
dp[2] = 3;
// 3. 状态转移方程
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + 2 * dp[i - 2];
}
// 4. 返回值
System.out.println(dp[n]);
count--;
}
}
}
