loommii935. 骑士拨号器
骑士在一张 n x n 的棋盘上巡视。在一个有效骑士巡视中，骑士可以从一个数字单元格开始，然后执行 n - 1 次移动，每次移动都必须是标准的骑士移动：呈 “L” 形状，即向一个方向移动两个单元格，然后垂直移动一个单元格，或向一个方向移动一个单元格，然后垂直移动两个单元格。
骑士只能站在数字单元格上（即蓝色单元格）。
给定一个整数 n，返回我们可以拨出的不同电话号码的数量。
因为答案可能很大，所以输出答案模 10^9 + 7。
示例 1：
输入：n = 1 输出：10 解释：我们需要拨出一个长度为 1 的数字，所以可以拨出 0-9，共 10 个数字。
示例 2：
输入：n = 2 输出：20 解释：所有可能的数字序列是：[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
示例 3：
输入：n = 3131 输出：136006598 解释：注意输出应当为模 10^9 + 7 的结果。
提示：
- 1 <= n <= 5000
func knightDialer(n int) int {
}动态规划思路：
- 定义状态：dp[i][j] 表示第 i 步时，以数字 j 结尾的方案数
- 状态转移：对于每个数字 j，找到它可以由哪些数字转移而来
- 初始状态：dp[0][j] = 1 (对于所有可达的数字 j)
骑士的移动规则决定了每个数字可以跳到的位置：
- 0 可以跳到 4, 6
- 1 可以跳到 6, 8
- 2 可以跳到 7, 9
- 3 可以跳到 4, 8
- 4 可以跳到 0, 3, 9
- 5 无法跳到任何位置
- 6 可以跳到 0, 1, 7
- 7 可以跳到 2, 6
- 8 可以跳到 1, 3
- 9 可以跳到 2, 4
func knightDialer(n int) int {
MOD := 1000000007
// 定义每个数字可以跳到的位置
jumps := [][]int{
{4, 6}, // 0
{6, 8}, // 1
{7, 9}, // 2
{4, 8}, // 3
{0, 3, 9}, // 4
{}, // 5 (无法跳到任何位置)
{0, 1, 7}, // 6
{2, 6}, // 7
{1, 3}, // 8
{2, 4}, // 9
}
// dp[i][j] 表示第 i 步时，以数字 j 结尾的方案数
prev := make([]int, 10)
for i := 0; i < 10; i++ {
prev[i] = 1
}
for step := 1; step < n; step++ {
curr := make([]int, 10)
for j := 0; j < 10; j++ {
for _, next := range jumps[j] {
curr[next] = (curr[next] + prev[j]) % MOD
}
}
prev = curr
}
result := 0
for i := 0; i < 10; i++ {
result = (result + prev[i]) % MOD
}
return result
}