方格走法

[编程题]方格走法

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

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

输入描述:

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

输出描述:

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

示例1

输入

3 2

输出

算法知识视频讲解

Python

小云云是真的很想学习

排列组合的问题， $C_{x+y}^x$ 一共要走 $x+y$ 步，哪 $x$ 步向右下走

def multiplication(a):
    if a == 1:
        return 1
    else:
        return a * multiplication(a - 1)
X, Y = map(int, input().split())
print(int(multiplication(X + Y) / (multiplication(X) * multiplication(Y))))

发表于 2019-11-05 15:34:21 回复(0)

Python

我要上岸！！

x, y = [int(n) for n in input().split()]
s = x + y
fenzi, fenmu = 1, 1
for i in range(x):
    fenzi *= (s-i)
for i in range(1, x+1):
    fenmu *= i
print(fenzi//fenmu)

发表于 2019-09-10 11:37:10 回复(0)

Python

贾志统

def func(x, y):
    x += 1
    y += 1
    dp = [1] * (x+1)
    for i in range(2, y+1):
        for j in range(2, x+1):
            dp[j] = dp[j] + dp[j-1]
    return dp[-1]


x, y = map(int, input().split())
result = func(x, y)
print(result)

发表于 2019-08-31 00:06:25 回复(0)

Python

找呀找呀找工作啦

import math
x,y=map(int,input().strip().split())
print(int(math.factorial(x+y)/math.factorial(x)/math.factorial(y)))

发表于 2019-08-08 16:51:01 回复(0)

Python

ElonB

""""
考虑动态规划
设dp[x][y]为x*y的网格，每次只能向两个方向，有以下规律：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
边界条件为 dp[i][j]=1，(当i=0或j=0)
"""
if __name__ == "__main__":
    x, y = map(int, input().strip().split())
    dp = [[1] * (y + 1) for _ in range(x + 1)]
    for i in range(1, x + 1):
        for j in range(1, y + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[x][y])

编辑于 2019-07-11 22:43:03 回复(0)