POJ 3731 Escape (组合数学)

在平面坐标上有一个格子,左下角是(0, 0),右上角是(X, Y),从起点(0, 0)到终点(x, y)有多少种行走方案,要求只能往前走和往右拐。

表示动态规划在下想不到。
因为起点很特殊,容易发现往右拐以后左边区域的所有点之后肯定是无法达到的,直接递推肯定是不行的,不妨枚举拐弯的次数,假如拐弯的次数时n,那么是n+1条直线构成的路径,假如往左方向的直线有p个,次方向可以容纳的直线个数为q个,那么这个方向贡献的次数是C(q, p),只需要将不同方向的方案数累乘起来就是拐点个数为n时的方案数。
注意一些细节的判断

 

LEAVE A COMMENT