2320. 外星遗迹的“坍塌迷宫”挑战
1000ms
256MB
简单
递推算法
题目描述
2090 年人类发现了一个智能生命留下的方格矩阵遗迹，边界在无穷远处。
行走规则如下：
1. 每一步只能从当前方格移动一格，走到相邻的方格上。
2. **走过的格子立即塌陷**，无法再走第二次。
3. 只能向**北、东、西**三个方向走（不能向南走）。
请计算：如果允许在方格矩阵上走 $n$ 步，共有多少种不同的方案？
输入格式
一行，包含一个正整数 $n$ ($n \le 20$)。
输出格式
一个整数，表示 $n$ 步后不同的方案总数。
样例 1
输入 (Input)
2
输出 (Output)
7
- 对于所有数据：$n \le 20$。
- **样例解释**：
走 2 步的方案如下（设起始点为 (0,0)）：
- 北 -> 北
- 北 -> 东
- 北 -> 西
- 东 -> 北
- 东 -> 东
- 西 -> 北
- 西 -> 西
共 7 种。注意“东 -> 西”和“西 -> 东”是不允许的，因为会回到原点（已塌陷）。
- **算法提示**：
本题可以使用递推或动态规划。
设 $f[i]$ 为走 $i$ 步的方案总数。
- 第 $i$ 步向北走：第 $i-1$ 步可以向任何方向走，方案数为 $f[i-1]$。
- 第 $i$ 步向东走：第 $i-1$ 步不能向西走。
- 第 $i$ 步向西走：第 $i-1$ 步不能向东走。
经过推导可得递推式：$f[i] = 2 \times f[i-1] + f[i-2]$，初始值 $f[0]=1, f[1]=3$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功