首页 > 试题广场 >

走方格的方案数

[编程题]走方格的方案数
  • 热度指数：129408 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

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

数据范围：



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


输出描述:
输出一行结果
示例1

输入

2 2

输出

6
算法知识视频讲解
添加回答
Python
心里的猫叫古怪头像 心里的猫叫古怪
动态规划解法： 
list1 = input().strip().split()
n = int(list1[0])#提取n  注意n是“横向”的格子数
m = int(list1[1])#提取m  注意m是“竖向”的格子数

#画图分析，到达某一个点的路线条数等于到达其相邻两个点的路线条数之和
#那我们依次求出到达每一个点的路线次数即可

#初始化一个二维列表，注意点：沿着棋盘格的边缘线走
#所以棋盘格的边缘线的相交点即为一个站点，也就是一个元素
#所以二维列表就要初始化为m+1行，n+1列，可画图观察
arr = [[0 for j in range(n+1)] for i in range(m+1)]
#不能走回头路，只能向右或向下
#所以在第一行的任意一个站点都只能有一条路到达，一路向右走
for i in range(n+1):
    arr[0][i] = 1
#在第一列的任意一个站点也只能有一条路到达，一路向下走
for i in range(m+1):
    arr[i][0] = 1
#依次求出到达每一个点的路线次数
for x in range(1,m+1):
    for y in range(1,n+1):
        arr[x][y] = arr[x][y-1] + arr[x-1][y]
#至此，到达每一个点的路线条数都计算出来了
#查询最后一个点的路线条数即可
#需要注意的是，最后一个点的坐标是arr[m][n]
print(arr[m][n])


发表于 2022-04-17 21:14:14 回复(0)
Python
牛客诶谁头像 牛客诶谁 
import sys

def dp_func(m, n):
    dp = [[0]*(n+1)]*(m+1)
    for i in range(m+1):
        dp[i][0] = 1
    for i in range(n+1):
        dp[0][i] = 1
    for i in range(1, m+1):
        for j in range(1, n+1):
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[m][n]

for line in sys.stdin:
    m, n = [int(i) for i in line.split()]

    # dp[m][n] = dp[m][n-1] + d[m-1][n]
    print(dp_func(m, n))

发表于 2021-05-02 14:47:39 回复(0)
Python
牛客314674748号头像 牛客314674748号
from functools import lru_cache
@lru_cache(maxsize=4000000)
def cal(n,m):
    if n == 0 and m == 0:
        return 1
    if n < 0 or m < 0:
        return 0
    return cal(n-1,m) + cal(n, m-1)

while True:
    try:
        n, m = map(int, input().split())
        print(cal(n, m))
    except:
        break
发表于 2021-04-20 20:00:06 回复(0)
Python
星凌九天头像 星凌九天
while True:
    try:
        n,m = map(int,input().split())
        a=1
        b=1
        c=1
        for i in range(1,n+m+1):
            a*=i
        for j in range(1,n+1):
            b*=j
        for k in range(1,m+1):
            c*=k
        num=a/(b*c)
        print(int(num))
    except:
        break
发表于 2021-03-18 10:48:42 回复(0)
Python
大溪地渔民头像 大溪地渔民
本题是数学题，一共走m+n步，其中m步是向右，求排列组合的数量 
import sys
from functools import reduce


for s in sys.stdin:
    m, n = map(int, s.split())
    m, n = (m, n) if m < n else (n, m)
    print(
        reduce(lambda x, y: x*y, range(m+n, n, -1), 1) // 
        reduce(lambda x, y: x*y, range(1, m+1), 1)
    )


发表于 2020-12-13 16:41:06 回复(0)
Python
玉鱼头像 玉鱼
o(m)空间的动态规划： 
while True:
    try:
        n, m = map(int, input().split())
        grid = [1]*(n+1)
        for i in range(1,m+1):
            for j in range(1,n+1):
                grid[j] += grid[j-1]
        print(grid[-1])
    except:
        break


发表于 2020-12-04 09:35:37 回复(0)
Python
乐观的lishan头像 乐观的lishan 
# 2020年11月15日09:46:14
def path_way(n, m):
    if n==0 or m==0:
        return 1
    else:
        return path_way(n-1, m) + path_way(n, m-1)

while True:
    try:
#       实际测试用例是一行空格输入，而不是题目中的两行，比如2 1
        n, m = map(int, input().split())
#         分两次读入是通不过的
#         n = int(input())
#         m = int(input())
        print(path_way(n, m))
    except:
        break
        

编辑于 2020-11-15 10:25:10 回复(0)
Python
辰c头像 辰c 
为什么这个不能AC？
n 和 m 这样写有啥问题吗？

while True:
    try:
        n = int(input())
        m = int(input())
        #  n, m = map(int, input().split())
        dp = [[1 for i in range(n + 1)] for j in range(m + 1)]
        dp[0][0] = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        # print(dp)
        print(dp[-1][-1])
        # print(max(dp[-1]))
    except:
        break

编辑于 2020-11-03 23:26:45 回复(2)
Python
whynotyeaaah头像 whynotyeaaah
排列组合问题：一共要走m+n步(向下走m步+向右走n步)，即在m+n步中选m步向下走。Cmm+n: 
while True:
    try:
        n, m = map(int, input().split())
        (maxx, minn) = (n, m) if n >= m else (m, n)
        nume = deno = 1
        for i in range(1, minn+1):
            nume *= (maxx+i)
            deno *= i
        print(nume//deno)
    except:
        break


发表于 2020-10-27 10:39:24 回复(0)
Python
牛客845373029号头像 牛客845373029号
python 递归
while True:
    try:
        n,m = map(int,input().split())
        def maxways(n,m):
            if n==0 or m==0:return 1
            return maxways(n-1,m) + maxways(n,m-1) 
        max1 = maxways(n, m)
        print(max1)
    except:
        break

发表于 2020-09-16 19:53:29 回复(0)
Python
zkzou头像 zkzou
为啥输入一定要是a,b = map(int,input().split())？？？
为啥一定要用while True？？？
发表于 2020-09-02 22:44:52 回复(0)
Python
JaquesJames头像 JaquesJames 
# 对于m*n的格子，就是从m+n步中选出m步向上或n步向右
# 因此为C(m+n,m)=C(m+n,n)种
from math import factorial
while True:
    try:
        n, m = map(int, input().split())
        print(int(factorial(n + m)/(factorial(n)*factorial(m))))
    except:
        break

发表于 2020-08-24 15:55:37 回复(0)
Python
牛客541939069号头像 牛客541939069号

有重复元素的排列问题（横向格子重复n次，纵向格子重复m次），计算公式为：
图片说明 

def perm(n):
    dot = 1
    for i in range(1,n+1):
        dot = dot * i 
    return dot

while True:
    try:
        [n,m] = list(map(int,input().split()))
        k = perm(m+n)/(perm(m)*perm(n))
        print(int(k))
    except:
        break
编辑于 2020-07-08 23:04:45 回复(0)
Python
^o^201903061215958头像 ^o^201903061215958
思路： 动态规划 
import sys

def f(n,m):
    if min(n,m)==1:
        return 1 + max(n,m)
    else:
        return f(n,m-1) + f(n-1,m)

for s in sys.stdin:
    s = s.strip().split(" ")
    r = f(int(s[0]), int(s[1]))
    print(r)


编辑于 2020-06-07 22:53:17 回复(0)
Python
朝夕_头像 朝夕_ 
def rec(m,n):
  dp = [[0 for i in range(n+1)]]*(m+1)
  for i in range(m+1):
    dp[i][0] = 1
  for i in range(n+1):
    dp[0][i] = 1
  for i in range(1,m+1):
    for j in range(1,n+1):
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
  return dp[m][n]
while True:
  try:
    a,b = map(int,input().split())
    print(rec(b,a))
  except:
    break

编辑于 2020-02-23 10:42:18 回复(0)
Python
谢小橙头像 谢小橙 
def walk(n,m):
    if n==0&nbs***bsp;m==0:
        return 1
    return walk(n-1,m)+walk(n,m-1)

while True:
    try:
        l=input().split()
        n=int(l[0])
        m=int(l[1])
        print(walk(n,m))
    except:
        break
用递归去做，通项公式为：f(n,m)=f(n-1,m)+f(n,m-1)，假设终点坐标为（n,m）。边界条件：当n==1或者m==1时，只有1种走法。
发表于 2020-02-21 16:28:44 回复(0)
Python
牛客757584655号头像 牛客757584655号
纯数学解法：
比如2 3的话，那么就是5步里面挑2步向一个方向走，剩余3步向另一个方向走。就是类似C5 2 这样的

正常这种题应该规定方格里面有几个地方不能走，避免这种O(M+N)的套公式计算法 
import sys

while True:
    line = sys.stdin.readline().strip()
    if not line:
        break
    n, m = int(line.split(' ')[0]), int(line.split(' ')[1])
    if n > m:
        n, m = m, n
    res = 1
    for i in range(n):
        res = res * (n + m - i)
    
    for j in range(n):
        res = res / (j + 1)
    print res
发表于 2020-02-15 06:12:03 回复(0)
Python
软粉头像 软粉
动态规划，坐标i,j只可能从左边或者上边移动过来，所以dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 
def chessboard(n, m):
    dp = [[1 for i in range(m+1)] for j in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
    return dp[-1][-1]


while True:
    try:
        n, m = map(int, input().split())
        print(chessboard(n, m))
    except:
        break

编辑于 2019-10-10 16:57:03 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

走方格的方案数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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