首页 > 试题广场 >

走方格的方案数

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

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

数据范围：



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


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

输入

2 2

输出

6
算法知识视频讲解
添加回答
Python 3
Scorpion201901072009417头像 Scorpion201901072009417
import sys
def countPath(n, m):
"""
dp函数：到达（n，m）的路径数量
base case (0, 0)为1，因为已经在目标位置，没有其他路径
"""
if n < 0 or m < 0:
return 0
if n == 0 or m == 0: # 到达棋盘的边缘，只有沿边一种走法
return 1

# 若非边缘情况，从上一个或左一个位置到达当前位置。
# ！！！注意：因为到达(n-1,m)或(n,m-1)时，此时只有一种选择到达（n,m)所以不需要再加1
return countPath(n - 1, m) + countPath(n, m - 1)

# 获取输入
line = input().split(' ')
n, m = int(line[0]), int(line[1])
print(countPath(n,m))

编辑于 2024-04-05 18:23:38 回复(0)
Python 3
牛客560069418号头像 牛客560069418号
如果目标点与起点不在一条水平或垂直直线上，创造两个新的目标点，分别横纵坐标-1，直到递归到在直线的情况，直线时只有一条路径。 
a = list(map(int,input().split()))
def loop(location):
    if not location[0]&nbs***bsp;not location[1]:
        return 1
    else:
        return loop([location[0] -1,location[1]]) + loop([location[0],location[1]-1])
print(loop(a))

发表于 2022-08-27 14:48:12 回复(0)
Python 3
进击的皮皮举头像 进击的皮皮举
递归法：
从m,n开始，向右走一步，m*n的方案数==(m-1)*n的方案数
向下走一步，m*n的方案数==m*(n-1)的方案数
由此得到递归式子：f(m,n)=f(m-1,n)+f(m,n-1)
在n=1时，方案数为m+1
在m=1时，方案数为n+1 
n,m=map(int,input().split())

def f(n,m):
    
    if n==1 :
        return m+1
    elif m==1:
        return n+1
    else:
        
        return f(n-1,m)+f(n,m-1)
print(f(n,m))


发表于 2022-08-15 16:33:43 回复(0)
Python 3
Justinshadow头像 Justinshadow 
def fun(n:int,m:int):
    if n == 0&nbs***bsp;m == 0:
        return 1
    else:
        return fun(n-1,m)+fun(n,m-1)

n,m = map(int,input().split())
print(fun(n,m))

发表于 2022-08-09 17:58:39 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
get_str = input().split(' ')
n, m = int(get_str[0]), int(get_str[1])
# (n+1)*(m+1)的二维dp数组
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        # dp数组初始化
        # 原点时0种走法
        if i==0 and j==0:
            dp[i][j] = 0
        # 从原点向下走一步共1种走法
        # elif i==0 and j==1:
        # 这里可以考虑优化？当退到左边界或上边界时仅剩一种走法
        elif i==0:
            dp[i][j] = 1
        # 从原点向右走一步共1种走法
        # elif i==1 and j==0:
        elif j==0:
            dp[i][j] = 1
        # [i][j]点的走法=左边一个点走法+上面一个点的走法
        # 即：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][m])

发表于 2022-07-30 17:46:31 回复(0)
Python 3
dk斗志昂扬头像 dk斗志昂扬 
#捋清了递归思想，这道题真是再简单不过了
def dp(a, b):
    if a > 0 and b > 0:
        return dp(a-1, b)+dp(a, b-1)
    else:
        return 1

n, m = map(int, input().split())
print(dp(n, m))

发表于 2022-07-19 01:09:03 回复(0)
Python 3
风软一江山头像 风软一江山
看起来像是一个递归问题 
def fun(n,m):
    if n == 1 and m == 1:
        return 2
    elif n == 1 and m != 1:
        return m+1
    elif n != 1 and m == 1:
        return n+1
    else:
        return fun(n-1,m) + fun(n,m-1)
a,b = map(int,input().split())
print(fun(a,b))


发表于 2022-06-30 17:12:52 回复(0)
Python 3
test8794头像 test8794
动态规划：
dp[i][j]代表i*j方格的方案数，归纳一下转移方程就可以了，比较简单。 
'''
Tag: 动态规划
'''

def walk_solutions(n, m):
    n += 1
    m += 1
    dp = [[0 for _ in range(n)] for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            if i == 1:
                dp[i][j] = j + 1
            elif j == 1:
                dp[i][j] = i + 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[i][j]

n, m = map(int, input().split())
print(walk_solutions(n, m))


发表于 2022-06-23 02:05:26 回复(0)
Python 3
鱼説头像 鱼説 
while 1:
    try:
        m,n = map(int,input().split())
        dp=[[0 for i in range(n+1)] for j in range(m+1)]
        for j in range(1,n+1):
            dp[0][j]=1
        for i in range(1,m+1):
            dp[i][0]=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]
        print(dp[m][n])
    except:
        break

发表于 2022-06-11 15:49:30 回复(0)
Python 3
小枫叶666头像 小枫叶666 
#参考：https://leetcode.cn/problems/unique-paths/solution/dai-ma-sui-xiang-lu-dong-gui-wu-bu-qu-xi-1vkb/
#DFS
m,n = map(int,input().split(" "))
directions=[(1,0),(0,1)]
def dfs(x,y):
#     pass
    if x > m&nbs***bsp;y > n:
        return 0
    
    if x == m and y == n:
        return 1
    return dfs(x+1,y)+dfs(x, y+1)
res = dfs(0,0)
print(res)


#DP
n,m = map(int,input().split(" "))
n=n+1
m=m+1
dp=[[0]*m for _ in range(n)] 
for j in range(m):
    dp[0][j] = 1
for i in range(n):
    dp[i][0] = 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[-1][-1])


发表于 2022-06-06 17:00:05 回复(0)
Python 3
xxooxx头像 xxooxx 
s = input().split(" ")
l = list(map(int,s))
a=l[0]
b=l[1]
ll = []

for i in range(0, l[0]+1):
    ll.append([1])
    for j in range(0, l[1]):
        ll[i].append(0)


for i in range(0, b+1):
    ll[0][i]=1



for i in range(1,a +1):  #hang
    for j in range(1, b+ 1):    #lie

            ll[i][j]=ll[i][j-1]+ll[i-1][j]

print(ll[a][b])

发表于 2022-06-02 13:59:28 回复(0)
Python 3
牛客31170954号头像 牛客31170954号
x, y = map(int, input().split())
A = ["0", "1"] #0往下，1往右
S = ["0", "1"]
while True:
    A = S
    k = 0
    for i in S:
        if len(i) < x + y:
            k += 1
    if k == 0:
        break
    for i in A:
        if len(i) < x + y:
            n = i.count("0")
            m = i.count("1")
            if i.count("0") < y:
                S.append(i + '0')
            if i.count("1") < x:
                S.append(i + '1')
        if len(i) < x + y:
            S.remove(i)
print(len(S))
发表于 2022-05-30 16:16:01 回复(0)
Python 3
牛客475421635号头像 牛客475421635号
def fun():
    a = [int(i) for i in input().split(" ")]
    b = [[0]*(a[0]+1) for i in range(a[1]+1)]
    for m in range(a[1]+1):
        for n in range(a[0]+1):
            if m != 0 and n == 0:
                b[m][n] = 1
            elif n != 0 and m == 0:
                b[m][n] = 1
            else:
                b[m][n] = b[m-1][n] + b[m][n-1]
    print(b[-1][-1])
    
if __name__ == "__main__":
    fun()
发表于 2022-05-22 00:40:47 回复(0)
Python 3
worldpuppy头像 worldpuppy 
m,n=input().split(' ')
d=1
s=1
for i in range(int(m)+1,int(m)+int(n)+1):
    d=d*i 
for i in range(1,int(n)+1):
    s=s*i 
print(round(d/s))

发表于 2022-05-18 19:18:54 回复(0)
Python 3
HeartBeating头像 HeartBeating 
#容易想到的是，在第一步时，可以选择向右或者向下，
#只需要当前的路径选择上加上(n,m−1)(n,m-1)(n,m−1)和(n−1,m)(n-1,m)(n−1,m)的矩阵路径选择即可。而(n,m−1)(n,m-1)(n,m−1)与(n−1,m)(n-1,m)(n−1,m)又是(n,m)(n,m)(n,m)的子问题，
#可以继续递归下去。
#只需要用iii，jjj表示当前位置，后续限制边界的向下或者向右即可。

def func(x,y):
    if x < 0&nbs***bsp;y < 0:
        return 0
    elif x == 0&nbs***bsp;y == 0:
        return 1
    else:
        return func(x-1, y)+func(x, y-1)

while True:
    try:
        a,b = map(int,input().split())
        c = func(a, b)
        print(c)
    except:
        break

发表于 2022-05-02 00:35:33 回复(0)
Python 3
牛客991913212号头像 牛客991913212号 
# 输入行数和列数
n,m=map(int,input().split(" "))
# 边界条件
# 当只有一行的时候
if m ==1:
    print(n+1)
# 当只有一列的时候
elif n ==1:
    print(m+1)
else:
    # 构建dp数组
    dp=[[1]*(n+1) for _ in range(m+1)]
    # print(dp)
    dp[0][1]=1
    dp[1][0]=1
    for i in range(1,m+1):
        for j in range(1,n+1):
            # 状态方程
            # 表示达到第i行第j列的方法
            dp[i][j]=dp[i-1][j] +dp[i][j-1]
    print(dp[m][n])

发表于 2022-04-28 12:58:22 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

走方格的方案数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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