题目描述
给你一个 (n) 行 (m) 列的二维迷宫，一开始你在迷宫的左上角的格子 ((1,1)) 处（我们用位置 ((x,y)) 来表示第 (x) 行第 (y) 列），你要走到右下角的格子 ((n,m)) 处 ，但是你是不能随便走的，每一步你只能往右移动一格，或者往下移动一个，并且你不能移动出迷宫的边界，请问你有多少种不同的移动方案。
说明：只要从起点到终点的移动路线不同，那么我们就说它们是不同的移动方案。比如：假设 (n = m = 2)，那么从左上角 ((1,1)) 移动到右下角 ((2,2)) 共有(2) 种移动方案：
- ((1,1) Rightarrow (1,2) Rightarrow (2,2))
- ((1,1) Rightarrow (2,1) Rightarrow (2,2))
输入格式
输入一行包含两个整数 (n,m(1 le n,m le 10)) ，以空格分隔。
输出格式
输出包含一个整数，表示从 ((1,1)) 走到 ((n,m)) 的方案数。
样例输入
2 2
样例输出
2
本题涉及算法：动态规划。
我们设状态 (f[i][j]) 表示从 ((1,1)) 走到 ((i,j)) 的方案总数；
那么：
- 对于 ((1,1)) 来说，(f[1][1] = 1) ；
- 对于除了 ((1,1)) 以外的所有第 (1) 行的元素 ((1,i)) 来说，因为 ((1,i)) 只有可能是从 ((1,i-1)) 走过来的，所以 (f[1][i] = f[1][i-1]) ;
- 对于除了 ((1,1)) 以外的所有第 (1) 列的元素 ((i,1)) 来说，因为 ((i,1)) 只有可能是从 ((i-1,1)) 走过来的，所以 (f[i][1] = f[i-1][1]) ;
- 对于其他的所有点 ((i,j)) ，因为 ((i,j)) 只能从 ((i-1,j)) 和 ((i,j-1)) 两个点走过来，所以 (f[i][j] = f[i-1][j] + f[i][j-1]) 。
我们可以按照这个思路递推得到 (f[n][m]) 就是我们的答案。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 11;
int n, m, f[11][11];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (i == 1 && j == 1) f[1][1] = 1;
else f[i][j] = f[i-1][j] + f[i][j-1];
}
}
cout << f[n][m] << endl;
return 0;
}
代码说明：因为所有的 (f[0][j]) 和 (f[i][0]) 都为 (0) , 所以对所有除了 ((1,1)) 以外的第一行或者第一列的元素 ((i,j)) ，我们同样可以使用推导方程：(f[i][j] = f[i-1][j] + f[i][j-1]) ，而不需要特殊判断。