难度: Hard
Submission
运行时间: 249 ms
内存: 16.1 MB
class Solution:
def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:
mod = 10**9+7
dp = [0,0,0,0]
dp[(source[1]==dest[1])*2+(source[0]==dest[0])]=1
mm = [
[n+m-4,n-1,m-1,0],
[1,m-2,0,m-1],
[1,0,n-2,n-1],
[0,1,1,0],
]
mmm = self.pow(mm, k)
return (dp[0]*mmm[3][0]+dp[1]*mmm[3][1]+dp[2]*mmm[3][2]+dp[3]*mmm[3][3])%mod
def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
c = [[0,0,0,0], [0,0,0,0],[0,0,0,0],[0,0,0,0]]
for i in range(4):
for j in range(4):
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]+ a[i][2] * b[2][j]+ a[i][3] * b[3][j]) % (10 ** 9 + 7)
return c
def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
res = [[1,0,0,0], [0,1,0,0],[0,0,1,0],[0,0,0,1]]
while n:
if n % 2:
res = self.multiply(res, a)
a = self.multiply(a, a)
n //= 2
return res
Explain
此题解利用矩阵快速幂的方式来解决在网格中从起点到终点的路径计数问题。首先定义了一个动态规划数组 dp，其初值基于起点和终点的相对位置。接着定义了转移矩阵 mm，它描述了在一步操作中各种状态（不同的行列位置关系）之间的转换。通过矩阵快速幂算法，计算 k 步后的状态转移矩阵 mmm。最终通过 mmm 和 dp 的乘积，得到了从起点到终点恰好 k 步的路径数量。
时间复杂度: O(log k)
空间复杂度: O(1)
class Solution:
def numberOfWays(self, n: int, m: int, k: int, source: List[int], dest: List[int]) -> int:
mod = 10**9+7 # 定义模数
dp = [0,0,0,0] # 初始化 dp 数组
# 根据源点和目的地是否在同一行列设置 dp 初始条件
dp[(source[1]==dest[1])*2+(source[0]==dest[0])]=1
# 定义状态转移矩阵
mm = [
[n+m-4,n-1,m-1,0],
[1,m-2,0,m-1],
[1,0,n-2,n-1],
[0,1,1,0],
]
mmm = self.pow(mm, k) # 计算 k 次幂的状态转移矩阵
# 计算最终结果
return (dp[0]*mmm[3][0]+dp[1]*mmm[3][1]+dp[2]*mmm[3][2]+dp[3]*mmm[3][3])%mod
def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
c = [[0,0,0,0], [0,0,0,0],[0,0,0,0],[0,0,0,0]]
for i in range(4):
for j in range(4):
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]+ a[i][2] * b[2][j]+ a[i][3] * b[3][j]) % (10 ** 9 + 7)
return c
def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
res = [[1,0,0,0], [0,1,0,0],[0,0,1,0],[0,0,0,1]]
while n:
if n % 2:
res = self.multiply(res, a)
a = self.multiply(a, a)
n //= 2
return res
Explore
在初始化dp数组时，使用的表达式`(source[1]==dest[1])*2+(source[0]==dest[0])`是为了编码起点和终点在行和列上的相对位置。这里dp数组有四种状态：第0个元素表示起点和终点既不在同一行也不在同一列，第1个元素表示起点和终点在同一列但不在同一行，第2个元素表示起点和终点在同一行但不在同一列，第3个元素表示起点和终点既在同一行也在同一列。因此，这种初始化方式是为了确定起点和终点的位置关系，并对应设置dp数组的初始值。
状态转移矩阵mm设计用于描述每一种状态（dp数组的四种状态）在一步移动后转换到其他状态的规则。每个元素mm[i][j]表示当前状态为i时，下一步转移到状态j的方法数。例如，mm[0][1]表示从状态0（起点和终点既不在同一行也不在同一列）转移到状态1（起点和终点在同一列）的方法数。这个矩阵基于网格的行和列的规则设计，比如从不同行列到同一行或同一列的转移，以及在同一行或列内部的移动。
使用模数10^9+7主要有两个原因：一是防止计算过程中整数溢出，特别是在处理大规模数据或长序列运算时；二是10^9+7是一个大质数，这在某些数学运算中可以减少冲突和提高计算效率，特别是在计算组合数学或哈希函数时。因此，它在算法问题中常被选用以保证结果的正确性和计算的高效性。
最终结果的计算涉及将经过k步后的状态转移矩阵mmm与初始化后的dp数组相乘。这里dp数组代表初态各位置关系的可能性，而通过状态转移矩阵mmm的k次幂，我们可以得到k步后各状态的可能性。最终，通过乘积求和的方式，我们可以得到从起点到终点恰好k步的所有可能路径的总数。具体来说，每个dp[i]与mmm中第3列的每个mmm[i][j]相乘后，求和结果即表示总的路径数，因为第3列的每个元素代表从初始状态i经过k步后到达终点的路径数量。