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

[饿掉鱼]

假设有栖在起点 $(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$ 时，有两种情况：

1. 不使用魔法，从 $(i-1,j)$ 转移而来。此时有 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。

2. 使用魔法，从 $(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时代