那就是两个函数: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~