骑士拨号器

骑士拨号器(medium)

做题过程

思路有的很快，但是因为测试集的数据会非常大，忘记给dp声明成long了，其实就是前面“骑士在棋盘上的概率”加个continue就行。

算法概述

原题

本题要求为把一个骑士放在拨号盘上，给定步数，计算有多少种号码的可能。使用 动态规划 。

• 时间复杂度为O(n)
• 空间复杂度为O(n)：还有棋盘大小的常系数

JAVA

class Solution {
    static int[][] dirs = {
        {-2, -1}, {-2, 1}, {2, -1}, {2, 1},
        {-1, -2}, {-1, 2}, {1, -2}, {1, 2}
    };

    public int knightDialer(int n) {
        long mod = 1000000007L;  // 使用 long 类型的取模数
        long[][][] dp = new long[n][4][3];  // 将 dp 数组的类型改为 long

        // 初始化第一步（step 0），跳过 (3,0) 和 (3,2)
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 3; ++j) {
                if ((i == 3 && j == 0) || (i == 3 && j == 2)) continue;
                dp[0][i][j] = 1;
            }
        }

        // 动态规划填充 dp 数组
        for (int step = 1; step < n; ++step) {
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if ((i == 3 && j == 0) || (i == 3 && j == 2)) continue;
                    for (int[] dir : dirs) {
                        int ni = i + dir[0], nj = j + dir[1];
                        // 检查新位置是否合法
                        if (ni >= 0 && ni < 4 && nj >= 0 && nj < 3 && (ni != 3 || nj != 0) && (ni != 3 || nj != 2)) {
                            dp[step][i][j] = (dp[step][i][j] + dp[step - 1][ni][nj]) % mod;
                        }
                    }
                }
            }
        }

        // 求最终的结果
        long sum = 0;  // sum 使用 long 类型
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 3; ++j) {
                if ((i == 3 && j == 0) || (i == 3 && j == 2)) continue;
                sum = (sum + dp[n - 1][i][j]) % mod;
            }
        }

        // 返回结果时，将 long 转换为 int
        return (int) sum;  // 显式转换 long 为 int
    }
}

总结

用的还是GPT的版本，因为GPT把初始化和动态规划部分分离了，虽然代码显得稍微冗长，但是从可维护性的角度是非常需要的优化，我缺乏这种思维。

还可以通过滚动数组优化空间复杂度