方格走法

[编程题]方格走法

热度指数：2669 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

输出一行，表示走法的数目

示例1

输入

3 2

输出

算法知识视频讲解

Python

牛客239836399号

s = input()
x = int(s.split()[0])
y = int(s.split()[1])
def foo(a, b):
    if a == 1 and b == 1:
        return 0
    if a == 1&nbs***bsp;b == 1:
        return 1
    return foo(a, b-1) + foo(a-1, b)
print(foo(x+1, y+1))

编辑于 2020-07-08 15:25:35 回复(0)

Python

ElonB

""""
动态规划，dp[x][y]表示所有走法的数目
到达x,y点的路径只有两条，从上边和从左边
dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
边界 dp[0][y] = dp[x][0] = 1
"""

if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[n][m])

发表于 2019-07-16 13:35:04 回复(0)