首页 > 试题广场 >

网格走法数目

[编程题]网格走法数目
  • 热度指数：20023 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有一个 X*Y 的网格，小团要在此网格上从左上角到右下角，只能走格点（也即格子的顶点）且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数 int x , int y ，请返回小团的走法数目。

数据范围：

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


输出描述:
输出包括一行，为走法的数目。
示例1

输入

3 2

输出

10
算法知识视频讲解
添加回答
Python
Linany头像 Linany
X,Y = map(int, input().split())
table = [[0 for col in range(X+1)] for row in range(Y+1)]
for row in range(Y+1):
    table[row][0] = 1
for col in range(X+1):
    table[0][col] = 1
for col in range(1, X+1):
    for row in range(1, Y+1):
          table[row][col] = table[row-1][col] + table[row][col-1]
print(table)
            
发表于 2018-09-23 11:29:52 回复(0)
Python
嘟嘟6668头像 嘟嘟6668
x=input().split(' ')
m=int(x[0])
n=int(x[1])
f=[[0 for i in range(0,n+1)] for j in range(0,m+1,1)]
for i in range(0,n+1):
    f[0][i]=1
for i in range(0,m+1):
    f[i][0]=1
for i in range(1,m+1):
    for j in range(1,n+1):
        f[i][j]=f[i-1][j]+f[i][j-1]
print(f[m][n])


发表于 2018-09-06 22:49:15 回复(0)
Python
zhepei头像 zhepei
python 解法 
# codiing:utf-8
import sys
x, y = list(map(int, input().split()))
record = [[0 for i in range(y+1)] for i in range(x+1)]
for i in range(x+1):
    for j in range(y+1):
        if i == 0 or j == 0:
            record[i][j] = 1
        else:
            record[i][j] = record[i][j-1] + record[i-1][j]
print(record[x][y])

编辑于 2018-09-03 16:12:56 回复(0)
Python
JemmyH头像 JemmyH 
x,y = input().split(" ")
x,y = int(x),int(y)
def add_d(x,y):
    if x == 0 or y == 0:
        return 1
    else:
        return (add_d(x - 1, y) + add_d(x, y -1))
print(add_d(x,y))
注意是从网格点走……
发表于 2018-08-11 15:53:03 回复(0)
Python
外卖老谭头像 外卖老谭 
import sys
x, y = sys.stdin.readline().strip().split(' ')
x = int(x)
y = int(y)
class a:
    def __init__(self):
        self.n = 0
    def findpath(self, i, j):
        if i == x and j == y:
            self.n += 1
        if i < x:
            self.findpath(i + 1, j)
        if j < y:
            self.findpath(i, j + 1)
        return self.n
tt = a()
print(tt.findpath(0, 0))

发表于 2018-08-09 21:42:02 回复(0)
Python
离疏头像 离疏 
x,y=list(map(int,input().split()))
def step(x,y):#递归方法
    if x==1 or y==1:#当某个方向只能走一步时，走法数目为x+y
        return x+y
    else:#两个方向都有多步可走时
        return step(x-1,y)+step(x,y-1)#先向其中一个方向走一步，问题减小为（x-1，y）规模和（x,y-1）规模，求和即可
ans=step(x,y)
print(ans)

发表于 2018-06-22 17:22:21 回复(0)
Python
华科平凡头像 华科平凡

python两种解法

直接使用公式：

from math import factorial as f
m, n = map(int, input().split)
print(f(n + m) / (f(m) * f(n)))

使用动态规划：path(m,n) = path(m,n-1)+path(m-1,n)

发表于 2018-04-13 16:22:07 回复(0)
Python
兜一圈就回去头像 兜一圈就回去
##逆推，推出每个点往前走有多少中走法，然后递归加起来就行了，注意第一行只能往左走，第一列只能往上走；
def get_way(m,n):
    if (m==0)&(n==0):
        return 0
    if (m==0)&(n!=0):
        return 1
    if (m!=0)&(n==0):
        return 1
    if (m!=0)&(n!=0):
        return get_way(m-1,n) + get_way(m,n-1)
    
x,y = map(int,input().split(' '))
s = get_way(x,y)
print (s)
发表于 2018-04-04 16:03:05 回复(0)
Python
牛客4740874号头像 牛客4740874号
def grid(x,y,i):
    if x==0 or y==0:
        return 0
    else:
        i[0]=i[0]+1
        grid(x-1,y,i)
        grid(x,y-1,i)
        
a=raw_input().split()
x=int(a[0])
y=int(a[1])
i=[0]
grid(x,y,i)
print i[0]+1
发表于 2018-03-21 14:12:48 回复(0)
Python
小欣8头像 小欣8 
if __name__ == '__main__':
    x, y = [int(x) for x in input().split()]
    n, m = x+1, y+1
    dp = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        dp[i][0] = 1
    for j in range(m):
        dp[0][j] = 1
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    print(dp[i][j])
发表于 2017-10-05 20:23:35 回复(0)
Python
R_12头像 R_12 
s=input().split()
down=int(s[0])
right=int(s[1])
ruselt=1
def popo(n):
    res=1
    while n!=1:
        res*=n
        n-=1
    return res
print(popo(down+right)//popo(right)//popo(down))
发现没人这么做，其实无非是向下几次，向右几次的组合，算一下组合数就好了
发表于 2017-08-31 16:41:47 回复(8)
Python
小水瓶头像 小水瓶 
def jiecheng(n):
    if n==1:
        return 1
    if n>1:
        return n*jiecheng(n-1)

m,n=map(int,input().strip().split(' '))
print(int(jiecheng(m+n)/jiecheng(m)/jiecheng(n)))
#排列组合问题
发表于 2017-08-22 11:49:09 回复(0)
提交观点

问题信息

动态规划 基础数学
难度：
12条回答 22303浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号