假设有栖在起点 $(0,0)$,终点在 $(n-1,m-1)$,我们设 $f_{i,j}$ 表示从起点 $(0,0)$ 到 $(i,j)$ 的合法路径数(这里 $i$ 表示横坐标,$j$ 表示纵坐标)。显然,当 $i=0$ 或 $j=0$ 时,$f_{i,j}=1$,因为只能向右或向上移动到达 $(i,j)$。当 $i>0$ 且 $j>0$ 时,有两种情况:
不使用魔法,从 $(i-1,j)$ 转移而来。此时有 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。
使用魔法,从 $(i+k,j)$ 或 $(i,j+k)$ 转移而来,其中 $k\in[1,\min(i,n-i),\min(j,m-j)]$。因为只能向左或向下转移,而且不能转移到地图外,所以 $k$ 的取值范围为 $\min(i,n-i)$ 和 $\min(j,m-j)$ 的交集。此时有 $f_{i,j}=\sum_{k=1}^{\min(i,n-i)}f_{i-k,j}+\sum_{k=1}^{\min(j,m-j)}f_{i,j-k}$。
最终的答案为 $f_{n-1,m-1}$。
时间复杂度:$O(nm\min(n,m))$。
大人时代变了,现在是AI时代