UniquePath 唯一路径

Last updated 6 years ago

问题

在 $n$ 行 $m$ 列的二维矩阵上从左上角移动到右下角 $[1,1] \rightarrow [n,m]$ ，每次移动只能向右/向下移动。求有多少种不同的路径。

Last updated 6 years ago

在 $n$ 行 $m$ 列的二维矩阵上从左上角移动到右下角 $[1,1] \rightarrow [n,m]$ ，每次移动只能向右/向下移动。求有多少种不同的路径。

设 $f(i,j)$ 为从 $[1,1]$ 到 $[i,j]$ 的不同路径的数量，其中 $i \in [1,n], j \in [1,m]$ 。因此有如下状态转移方程：

f(i,j) = \begin{cases} 0 & (initialize) & i \in [0,n], j \in [0,m] \\ 1 & (initialize) & i = j = 1 \\ f(i-1,j) + f(i,j-1) & (loop) & i \in [1,n], j \in [1,m] \end{cases}

$(1)$ 初始化，设 $f(1,1) = 1$ ，认为从 $[1,1]$ 到 $[1,1]$ 的路径有1条，实际编码是设 $f(0,1)=f(1,0)=f(1,1)=1$ ；

$(2)$ 对于节点 $[i,j]$ ，既可以从上方 $[i,j-1]$ 过来，也可以从左方 $[i-1,j]$ 过来。因此 $f(i,j) = f(i-1,j)+f(i,j-1)$ ；

$f(n,m)$ 即为从 $[1,1]$ 到 $[n,m]$ 的不同路径的数量。该算法的时间复杂度是 $O(n \times m)$ 。

设 $f(i,j)$ 为从 $[1,1]$ 到 $[i,j]$ 的不同路径的数量，其中 $i \in [1,n], j \in [1,m]$ 。因此有如下状态转移方程：

f(i,j) = \begin{cases} 0 & (initialize) & i \in [0,n], j \in [0,m] \\ 1 & (initialize) & i = j = 1 \\ f(i-1,j) + f(i,j-1) & (loop) & i \in [1,n], j \in [1,m] \end{cases}

$(1)$ 初始化，设 $f(1,1) = 1$ ，认为从 $[1,1]$ 到 $[1,1]$ 的路径有1条，实际编码是设 $f(0,1)=f(1,0)=f(1,1)=1$ ；

$(2)$ 对于节点 $[i,j]$ ，既可以从上方 $[i,j-1]$ 过来，也可以从左方 $[i-1,j]$ 过来。因此 $f(i,j) = f(i-1,j)+f(i,j-1)$ ；

$f(n,m)$ 即为从 $[1,1]$ 到 $[n,m]$ 的不同路径的数量。该算法的时间复杂度是 $O(n \times m)$ 。