娱乐 （红包）算法挑战一则——到达终点的方法种类

[fangaa]

用Dp倒是不难，不过你要的是数学结论吗？

[fangaa]

7 小时前，reflectK说道:

第一题应该可以有结论

第二题只需要dp方程就可以了

那就是两个函数：f(m,n)是走一个mXn网格的路径数，g(m,n,x,y)是走一个mXn网格但不经过点(x,y)的路径数。那么f(m,n)=C(m+n,m)，而g(m,n,x,y)=f(m,n)-f(x,y)*f(m-x,n-y)。

那后三个就是

1. f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')+g(m,n,x,y)

2. f(x,y)*f(m-x',n-y')+g(m,n,x,y)

3. f(m,n)-f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')

反倒是魔法那个麻烦点，干脆想成mXnX3三层立体的。从中间层开始，上面那层整体向上移一格，下面那层整体向右移一格，然后就正常DP~

二月 14, 2023，由fangaa修改