描述

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围：1≤n,m≤8 


输入描述：

输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述：

输出一行结果

示例1

输入： 
2 2

输出： 
6


递归实现（Python）： 
#坐标为（a,b）的坐标点只能从左边的（a-1，b）和上边的（a，b-1）到达
#于是直接递归即可，注意递归出口为行或者列数为1的时候
def f(a,b):
    if a==1 or b==1:
        return 1
    else:
        return f(a-1,b)+f(a,b-1)
str1=input().split()
n=int(str1[0])
m=int(str1[1])
print(f(n+1,m+1))#n和m是格子数，行数列数比格子数大1
动态规划实现（C++）： 
//主题：
//思路：坐标为（a,b）的坐标点只能从左边的（a-1，b）和上边的（a，b-1）到达
//得到状态转移方程，f（a,b）=f（a-1，b）+f（a，b-1） 
#include<bits/stdc++.h>
using namespace std;
int dp[10][10]; 
int main(){
	int n,m;
	cin>>n>>m;
	//第一行全1 
	for(int i=1;i<=n+1;i++){
		dp[i][1]=1;
	}
	//第一列全1 
	for(int i=1;i<=m+1;i++){
		dp[1][i]=1;
	}
	//开始打表 
	for(int i=2;i<=n+1;i++){
		for(int j=2;j<=m+1;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1];
			//cout<<dp[i][j]<<" ";
		}
		//cout<<endl;
	}
	cout<<dp[n+1][m+1];
	return 0;
}