Description

在XxY的方格中,以左上角格子为起点,右下角格子为终点,每次只能向下走或者向右走,请问一共有多少种不同的走法

给定两个正整数int x,int y,请返回走法数目。保证x+y小于等于12。

测试样例:

2,2
返回:2

Solutions

1. 排列组合

  直接计算 C(x, x+y) 即可。

from math import factorial
class Robot:
    def countWays(self, x, y):
        return factorial(x + y - 2) / (factorial(x - 1) * factorial(y - 1))  # 步数比层数少一

References

  1. 9.2 方格移动