信息奥赛题解｜踩方格
🚀 题目浏览
【题目描述】
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走 $n$ 步，共有多少种不同的方案。（$2$ 种走法只要有一步不一样，即被认为是不同的方案）
【输入】
允许在方格上行走的步数 $n(n \le 20)$。
【输出】
计算出的方案数量。
【输入样例】
2【输出样例】
7【原题链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1196
☘️ 题解分析
本题是递推问题的经典问题之一，属于 「全局移动路线方案数」问题。
在之前的题解中，我们已经讲解了「单点移动路线」问题，其目标是求到达 某一个点 的方案数，但并没有涉及走到该点的步数；而本题的「全局移动路线」则是给定步数，求解所有该步数内能够走的不同路线数量。
附：单点移动路线问题相关题解
主站点：
【信息奥赛题解】移动路线（详细分析题解 & C++ 代码）
【信息奥赛题解】过河卒（详细分析题解 & C++ 代码）备用站点：
在本题中，我们假设 f[n] 为 走 n 步的不同路线总数，那么这个 f[n] 可以拆分成 3 个独立的部分：
- 最后一步 向 左 走的路线数
l[n] - 最后一步 向 右 走的路线数
r[n] - 最后一步 向 上 走的路线数
u[n]
即 f[n] = l[n] + r[n] + u[n] ，所以我们可以通过计算 l[n], r[n], u[n] 来得到 f[n]
而对于 l[n]，r[n], u[n] ，我们可以由 f[n - 1] 来推断。
按照我们的假设， f[n-1] 表示 走 n-1 步的不同路线总数，由于这里面的每条路线都是不同的，所以在这些路线的基础上，再往左走 1 步，得到的路线也都是不同的，就有 l[n] = f[n-1] ❌
但是我们知道 并不是所有路线，都能再往左走的。在所有走 n -1 步的路线中，如果第 n - 1步是往右走的，就 没有办法在第 n 步的时候往左走的，因为左边的方格塌陷了。
所以 只有第 n - 1步往左走，或者往上走的路线，才能在第 n 步时，往左走。
而 所有 n -1步 往左走的路线数量，按照我们的假设，就等于 l[n-1]；所有 n -1步 往上走的路线数量，按照我们的假设，就等于 u[n-1] 。所以 l[n] = l[n - 1] + u[n-1] ✅
同理，r[n] = r[n-1] + u[n-1] ✅
u[n] 比较特殊，因为 n-1 步往左、往右的路线在走第 n 步时，均可以向上走，所以 u[n] = l[n-1] + r[n-1] + u[n-1]=f[n-1] ✅
边界条件很好确定，l[1] = r[1] = u[1] = 1，因此就可以由递推关系，推出 l[2],l[3], ... ,l[n]，同理推出 r[2],r[3], ... ,r[n] 和 u[2],u[3], ... ,u[n] 🎉
最后再计算，$f[n] = l[n] + r[n] + u[n]$ 即可得到答案。
本题还可以简化，不过该简化式一下子不容易想到，需要用一些数学知识，推导如下：
$f[n]$
$= l[n] + r[n] + u[n]$
$= 2 * l[n -1] + 2 * r[n-1] + 3 * u[n-1]$
$= 2 * f[n-1] + u[n-1]$
$= 2 * f[n-1] + u[n-2] + l[n -2] + r[n - 2]$
$= 2 * f[n-1] + f[n-2]$
即递推式为 $f[n] = 2 * f[n - 1] + f[n-2](n \ge 3)$
🍉 总结：该题从 不同路线 和 路线的第 n 步和 n-1 步方向 角度去展开递推，会比较清晰明了（不建议像「单点移动路线」问题那样从某个点开始考虑）
🧑🏻💻 C++ 代码
标准版
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
typedef long long ll;
int n;
ll f[N], l[N], r[N], u[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
//边界条件
l[1] = r[1] = u[1] = 1;
f[1] = l[1] + r[1] + u[1];
//递推
for (int i = 2; i <= n; ++i) {
l[i] = l[i - 1] + u[i - 1];
r[i] = r[i - 1] + u[i - 1];
u[i] = l[i - 1] + r[i - 1] + u[i - 1];
f[i] = l[i] + r[i] + u[i];
}
cout << f[n] << endl;
return 0;
}优化版
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30;
int n;
ll f[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
//数学简化后的递推
f[1] = 3;
f[2] = 7;
for (int i = 3; i <= n; ++i) { //注意i从3开始
f[i] = 2 * f[i - 1] + f[i - 2];
}
cout << f[n] << endl;
return 0;
}
