题目描述

有一张 m×n 个小方格的地图，一个机器人位于地图的左上角（如图标记为 Start 的地方），它每步只能向右或者向下移动一格，如果走到右下角的终点（如图标记为 Finish 的地方），有多少种不同的方法？

例如，一个 3×2 的地图，方法数是 3 种，分别是：
右 → 右 → 下
右 → 下→ 右
下 → 右 → 右

最优解法：动态规划

动态规划，先初始化第一行和第一列的所有格子为1，格子内的数表示到当前格子的路径数，到第一行和第一列格子的路径只有1条，然后从第2行第2列开始，每个格子的路径数等于他上方格子的路径数加左方格子的路径数，直到填写完最后一个格子

#include<iostream>
using namespace std;
int main(){
	int x,y;
	cin>>x>>y;
	
	//动态初始化二维数组 
	int **dp = new int*[x];
	for(int i=0;i<y;i++)
	{
		dp[i]=new int[y]; 
	}

//	int dp[100][100]; 
	
	//将第一列初始化为 1 
	for(int i=0;i<x;i++)
	{
		dp[i][0]=1;	
	}
	//将第一行初始化为 1
	for(int i=0;i<y;i++)
	{
		dp[0][i]=1;	
	} 
	
	//从第二行第二列开始遍历,每个格子代表到达的路径数
	for(int i=1;i<x;i++)
	{
		for(int j=1;j<y;j++)
		{
			dp[i][j]=dp[i][j-1]+dp[i-1][j];
		}
	}
	
	cout<<dp[x-1][y-1]; 
	
}

递归求解

当x，y大于17后，递归求解方法不适用，递归函数调用消耗太多内存

#include<iostream>
using namespace std;

int f(int x,int y,int t_x,int t_y);

int main(){
	int x,y;
	cin>>x>>y;
	int num = f(0,0,x-1,y-1);
	cout<<num<<endl;
}

int f(int x,int y,int t_x,int t_y)
{
	if(x>t_x||y>t_y)
		return 0;
	if(x==t_x||y==t_y)
		return 1;
	int n1 = f(x+1,y,t_x,t_y);
	int n2 = f(x,y+1,t_x,t_y);
	return n1+n2;
}