935. 骑士拨号器

作者:江月迟迟

发表于:2024-12-10

字数统计:717 字

预计阅读3分钟

思路

题解

/**
 * @param {number} n
 * @return {number}
 */
//  回溯，但是超时
var knightDialer = function(n) {
    const result = [], path = []
    let count = 0
    const m = 4
    const n1 = 3
    const matrix = Array(m).fill().map(() => Array(n1).fill(1))
    matrix[3][0] = 0
    matrix[3][2] = 0
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n1; j++) {
            if(matrix[i][j] === 1) dfs(i, j)
        }
    }
    return count

    function dfs(i, j) {
        if(i < 0 || i >= m || j < 0 || j >= n1) return
        if(path.length === n) {
            count = (count + 1) % 1000000007
            return
        }
        if(matrix[i][j] === 0) return
        path.push(matrix[i][j])
        dfs(i+1, j+2)
        dfs(i+1, j-2)
        dfs(i+2, j+1)
        dfs(i+2, j-1)
        dfs(i-1, j-2)
        dfs(i-1, j+2)
        dfs(i-2, j-1)
        dfs(i-2, j+1)
        path.pop()
    }
};

// 回溯，简单优化
var knightDialer = function(n) {
    const MOD = 1000000007;
    const directions = [
        [1, 2], [1, -2], [-1, 2], [-1, -2],
        [2, 1], [2, -1], [-2, 1], [-2, -1]
    ];
    const m = 4, n1 = 3;
    let count = 0;

    // 初始化电话键盘
    const matrix = Array(m).fill().map(() => Array(n1).fill(1));
    matrix[3][0] = 0;
    matrix[3][2] = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n1; j++) {
            if (matrix[i][j] === 1) {
                dfs(i, j, n - 1);
            }
        }
    }
    return count;

    function dfs(i, j, remainingMoves) {
        if (i < 0 || i >= m || j < 0 || j >= n1 || matrix[i][j] === 0) return;
        if (remainingMoves === 0) {
            count = (count + 1) % MOD;
            return;
        }

        for (const [dx, dy] of directions) {
            dfs(i + dx, j + dy, remainingMoves - 1);
        }
    }
};

// 发现n方的时间复杂度超出了这道题范围，如想使用回溯，必须减少重复计算，我们可以使用记忆化搜索
// 发现子问题是从位置pos开始跳step步，所可以拥有的方案数memo[pos][step]
var knightDialer = function(n) {
    const MOD = 1000000007;

    // 从每个数字可以跳到哪些数字
    const moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [3, 9, 0],
        5: [], // 5 不在跳跃范围内
        6: [1, 7, 0],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    };

    // 缓存结果：memo[pos][steps]
    const memo = new Array(10).fill(0).map(() => new Array(n).fill(-1));

    let count = 0;
    for (let i = 0; i <= 9; i++) {
        count = (count + dfs(i, n - 1)) % MOD;
    }
    return count;

    function dfs(pos, steps) {
        if (steps === 0) return 1; // 基础情况：剩余 0 步时，计为 1 种
        if (memo[pos][steps] !== -1) return memo[pos][steps]; // 返回缓存结果

        let result = 0;
        for (const next of moves[pos]) {
            result = (result + dfs(next, steps - 1)) % MOD;
        }
        memo[pos][steps] = result; // 缓存结果
        return result;
    }
};

// 动态规划
var knightDialer = function(n) {
    const MOD = 1000000007;

    // 从每个数字可以跳到哪些数字
    const moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [3, 9, 0],
        5: [], // 5 不在跳跃范围内
        6: [1, 7, 0],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    };

    // dp[i][pos]: 拨打长度为 i+1 的号码时，骑士位于 pos 的电话号码数量
    let dp = new Array(10).fill(1); // 初始长度为 1，每个数字都只有 1 种可能

    for (let step = 1; step < n; step++) {
        const nextDp = new Array(10).fill(0);
        for (let pos = 0; pos <= 9; pos++) {
            for (const next of moves[pos]) {
                nextDp[next] = (nextDp[next] + dp[pos]) % MOD;
            }
        }
        dp = nextDp; // 更新当前状态
    }

    // 总和
    return dp.reduce((sum, count) => (sum + count) % MOD, 0);
};