01-网格走法 Python

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

1、题目描述

有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。

输入描述:

输入包括一行，逗号隔开的两个正整数x和y，取值范围[1,10]。

输出描述:

输出包括一行，为走法的数目。

示例1

输入

3 2

输出

2. 思路分析

该题与“走台阶“的题目异曲同工。
根据题目描述，走格时只能向下走或向右走。则假若目标格为（x，y），那么走向目标节点的走法就有两种，分别是：
（1）由（x-1，y）格向下走
（2）由（x，y-1）格向右走
所以，对与边界的格子来说，都只有上述的这两种走法，所以走向（n,m)格的总走法数目，就是【其上方格点的走法数目】与【其左方格点的走法数目】的和。此时假设函数f(x,y)表示走向格点(x,y)的走法数目，那么能够得到：

f(x,y)=f(x−1,y)+f(x,y−1)

3.Python实现

# 递归
# f(x,y) = f(x-1,y)+f(x,y-1)x, y = map(int, input().split())
def fun(x,y):
if x==1 or y==1:
return x+y
else:
return fun(x-1,y)+fun(x,y-1)ret = fun(x,y)
print(ret)