骑士拨号器
难度:
标签:
题目描述
象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
象棋骑士可能的移动方式如下图所示:
我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
因为答案可能很大，所以输出答案模 109 + 7.
示例 1：
输入：n = 1 输出：10 解释：我们需要拨一个长度为1的数字，所以把骑士放在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 解释：注意取模
提示：
1 <= n <= 5000
代码结果
运行时间: 101 ms, 内存: 0.0 MB
/*
题目思路：
使用Java Stream实现同样的功能。
这里我们依然用动态规划的思想，但利用Stream的特性进行一些优化。
我们将MOVES和dp数组以Stream的方式处理。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class KnightDialerStream {
private static final int MOD = 1000000007;
private static final int[][] MOVES = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
public int knightDialer(int n) {
long[] dp = new long[10];
Arrays.fill(dp, 1);
for (int j = 1; j < n; j++) {
long[] next = new long[10];
IntStream.range(0, 10).forEach(i -> next[i] = Arrays.stream(MOVES[i]).mapToLong(k -> dp[k]).sum() % MOD);
dp = next;
}
return (int) (Arrays.stream(dp).sum() % MOD);
}
}
解释
方法:
该题解使用矩阵快速幂的方法来解决骑士拨号器问题。首先构建一个10x10的转移矩阵，矩阵中的每个元素 mat[i][j] 表示从数字 i 跳到数字 j 的合法性（1表示合法，0表示不合法）。然后利用矩阵快速幂算法，将转移矩阵mat的n-1次方与初始状态向量相乘，得到从各个起点跳n-1次后到达各个数字的方案数。最后将这些方案数相加并取模，就得到了最终答案。
时间复杂度:
O(logn)
空间复杂度:
O(1)
代码细节讲解
🦆
在构建转移矩阵时，怎样确定每个元素的值，特别是从一个数字到另一个数字是否合法的判断基于哪些规则？
▷🦆
矩阵快速幂算法在这个问题中是如何应用的？具体来说，怎样通过快速幂算法加速转移矩阵的幂次计算？
▷🦆
在代码中，为什么在快速幂的过程中要对矩阵进行模操作，模操作的目的是什么？
▷🦆
题解中提到初始状态向量，但在代码示例中没有明显看到这一部分的实现。初始状态向量应该如何构建，并如何应用于矩阵快速幂的结果？
▷