※ 引述《ZooseWu (动物园 公告)》之铭言：
: 935. Knight Dialer
: 西洋棋的骑士只能往前两步后往左或右走一步
: 有一个拨号板如下图
: https://assets.leetcode.com/uploads/2020/08/18/phone.jpg
: 骑士只能站在数字上(蓝色按钮)
: 回传骑士在拨号板上能走的所有可能的数量mod 10^9+7
: Input: n = 1 Output: 10
: 每一格都可以踩 共十种
: Input: n = 2 Output: 20
: 所有可以走的路径是
: [04, 06, 16, 18, 27, 29, 34, 38, 40, 43,
: 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
思路差不多 dp[i][j] 代表以数字 i 为结尾 长度是 j 的方法数
像 3 能走到 4, 8
那下一轮的 dp[4][j+1], dp[8][j+1] 就要加上这轮的 dp[3][j]
实际上 j 也不是必要的 因为前面轮数的结果用不到
所以只要记两轮 也就是这一轮和下一轮的结果就好
Python code:
class Solution:
def knightDialer(self, n: int) -> int:
dp = [1]*10
mod = 10**9+7
edge = [(0,4), (0,6), (1,6), (1,8), (2,7), (2,9), (3,4), (3,8),
(4,9), (6,7)]
for _ in range(n-1):
newdp = [0]*10
for a, b in edge:
newdp[a] += dp[b] % mod
newdp[b] += dp[a] % mod
dp = newdp
return sum(dp) % mod
然后看讨论区才发现有个 O(logn) 的做法
因为每一轮的状态转移是固定的
可以直接把矩阵列出来 也就是
[[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0]]
第一行就代表数字 0 下一轮可以变成 4, 6
进行 n 轮就等于是初始状态 [1,1,1,1,1,1,1,1,1,1]
乘这个矩阵 n-1 次
所以就可以用快速幂 O(logn)
lee真的好强==