执行结果:通过

执行用时和内存消耗如下：

代码如下： 

#define MOD 1000000007int knightDialer(int n) {int moves[10][4] = {{4, 6, -1, -1},{6, 8, -1, -1},{7, 9, -1, -1},{4, 8, -1, -1},{3, 9, 0, -1},{-1, -1, -1, -1},{1, 7, 0, -1},{2, 6, -1, -1},{1, 3, -1, -1},{2, 4, -1, -1}};int d[2][10] = {0};for (int i = 0; i < 10; i++) {d[1][i] = 1;}for (int i = 2; i <= n; i++) {int x = i & 1;for (int j = 0; j < 10; j++) {d[x][j] = 0;for (int k = 0; moves[j][k] != -1; k++) {d[x][j] = (d[x][j] + d[x ^ 1][moves[j][k]]) % MOD;}}}int res = 0;for (int i = 0; i < 10; i++) {res = (res + d[n % 2][i]) % MOD;}return res;
}

解题思路：

1. 定义骑士的移动路径：
   • 首先，需要明确骑士在每个数字上能够移动到的下一个数字。使用moves数组来表示每个数字能够移动到的下一个数字的集合。例如，数字0可以移动到数字4和6，数字1可以移动到数字6和8，依此类推。不存在的移动用-1表示。
2. 动态规划初始化：
   • 使用一个二维数组d来存储每一步在每个数字上能够到达的不同路径的数量。数组d的第一维表示步数（奇数和偶数步分别用两个子数组表示以减少空间复杂度），第二维表示数字（0到9）。
   • 初始化时，对于第一步（i=1），每个数字都只能从自己出发，所以每个数字上的路径数量都为1。
3. 动态规划状态转移：
   • 从第二步开始，对于每一步和每一个数字，计算到达该数字的不同路径的数量。这是通过遍历所有可以从当前数字出发到达的下一个数字，并累加这些下一个数字在上一步的路径数量来实现的。
   • 为了减少空间复杂度，使用滚动数组技巧，只保留当前步和上一步的信息，通过i & 1和x ^ 1来切换当前步和上一步的数组。
4. 结果汇总：
   • 最后，将所有数字在n步时的路径数量相加，得到总路径数量，并对MOD取模，以防止整数溢出。

关键点

• 动态规划：使用动态规划来记录每一步在每个数字上的路径数量，避免重复计算。
• 滚动数组：利用滚动数组技巧来减少空间复杂度，使空间复杂度从O(n * 10)降低到O(10)。
• 取模运算：每一步的累加结果都对MOD取模，以防止整数溢出。

复杂度分析

• 时间复杂度：O(n * 10 * 4)，因为对于每一步（n步），每个数字（10个）最多有4个可能的下一个数字。
• 空间复杂度：O(10)，使用滚动数组技巧，只保留当前步和上一步的信息。