[leetcode/lintcode 題解] 算法面試真題詳解：騎士撥号器

描述

國際象棋中的騎士可以按下圖所示進行移動：

這一次，我們将 “騎士” 放在電話撥号盤的任意數字鍵（如上圖所示）上，接下來，騎士将會跳 N-1 步。每一步必須是從一個數字鍵跳到另一個數字鍵。

每當它落在一個鍵上（包括騎士的初始位置），都會撥出鍵所對應的數字，總共按下 N位數字。

你能用這種方式撥出多少個不同的号碼？

因為答案可能很大，是以輸出答案模 10^9 + 7。

1≤N≤5000

線上評測位址：

領扣題庫官網

樣例1
輸入：1
輸出：10
說明：
答案可能是0,1,2,3, ... , 9，           

樣例2
輸入：2
輸出：20
說明：
答案可能是04, 06, 16, 18, 27, 29, 34, 38, 43, 49, 40, 61, 67, 60, 72, 76, 81, 83, 94, 92。           

樣例3
輸入：3
輸出：46           

題解

本題采用

動态規劃

的方法，考慮每一步棋子變化的狀态，進行統計。我們可以使用滾動數組節省空間

class Solution {
    public int knightDialer(int N) {
        int MOD = 1_000_000_007;
        int[][] moves = new int[][]{
            {4,6},{6,8},{7,9},{4,8},{3,9,0},
            {},{1,7,0},{2,6},{1,3},{2,4}};

        int[][] dp = new int[2][10];
        Arrays.fill(dp[0], 1);
        for (int hops = 0; hops < N-1; ++hops) {
            Arrays.fill(dp[~hops & 1], 0);
            for (int node = 0; node < 10; ++node)
                for (int nei: moves[node]) {
                    dp[~hops & 1][nei] += dp[hops & 1][node];
                    dp[~hops & 1][nei] %= MOD;
                }
        }

        long ans = 0;
        for (int x: dp[~N & 1])
            ans += x;
        return (int) (ans % MOD);
    }
}           

更多題解參考：

九章官網solution