问题：

有一个X*Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请问机器人一共有多少种走法。 

输入在一行给出n，m代表n行m列的网格，n<=6,m<=6。

输出在一行给出方法数。

思路：

与上楼梯问题一样，我们先从小规模可以解决的问题开始考虑。

情况1: 1行1列

1

方法数为1。

情况2:1行2列

1

1

方法数为1。

情况3: 2行1列

1

1

方法数为1。

情况4: 2行2列

1	1
1	2

方法数为2。

情况5: 3行2列

1	1
1	2
1	3

方法数为3。

情况6：2行3列

1	1	1
1	2	3

方法数为3。

情况7：3行3列

1	1	1
1	2	3
1	3	6

方法数为6。

至此，可以初步发现一些规律，走到当前格的方法数为走到左边一个的方法数加上走到上边一个的方法数，并且只要是第一行或者第一列，走到当前格的方法数一定是1。依然写出递推公式：

f(x,y) = f(x-1,y) + f(x,y-1) (x,y)为二维数组的坐标

递归代码如下:

#include <bits/stdc++.h>
using namespace std;
int solve(int x,int y); 
int main() {
	int n,m;
	cin >> n >> m;
	cout << solve(n,m) << endl;
	return 0;
} 

int solve(int x,int y) {
	if(x==1 || y==1) return 1;
	return solve(x-1,y) + solve(x,y-1);
}

一如既往的简洁，但是单看代码却很难推出思考过程，下面给出迭代的代码：

#include <bits/stdc++.h>
using namespace std;
int solve(int x,int y); 
int dp[7][7];
int main() {
	int n,m;
	cin >> n >> m;
	cout << solve(n,m) << endl;
	return 0;
} 

int solve(int n,int m) {
	dp[1][1] = 1;
	for(int i=1;i<=m;i++) 
		dp[1][i] = 1;
	for(int i=1;i<=n;i++) 
		dp[i][1] = 1;
	for(int i=2;i<=n;i++) 
		for(int j=2;j<=m;j++)
			dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
	return dp[n][m];
}

依然是同样的思考方式的两种不同表现方式，递归倒着写，迭代顺着写。后者更符合人脑的思考逻辑且性能更高，这里用上了二维数组，之所以用二维数组，是因为x和y都是变量，在推理的过程中可可以发现，应该要使用二维来记录当前到达当前坐标的方法数。

分享一句从up那里听到的话，“人理解迭代，神理解递归”hhh。笔者认为，想要写出完美的递归代码，还是要从小规模的问题着手思考，先用迭代思路走一遍，毕竟只有走过艰难的路（迭代），登顶之后，才能站在更高的角度（递归）来解决问题。