Leetcode 935 - Knight Dialer

題目

Problem#

你能操縱一個西洋棋的騎士(Knight)旗子，它只能走 L 字形。

有一個數字鍵盤，從 0 到 9 是可以走的格子，* 和 # 不能走，你只能照騎士的走法去走去組合電話號碼，給你一個數字 n 代表電話號碼長度，問你能不能回傳最多有幾種不同電話號碼組合?

測資限制#

• $1 \le n \le 5000$
• 移動總共 n-1 次
• 答案可能很大要 mod $10^9+7$

想法#

先從 n = 1 開始想，每個格子的可能的走法是以下情況:

// n = 1
2 2 2
3 0 3
2 2 2
x 2 x

接著試著求出 n = 2 的組合數，以 1 號格子為例，可以到達它的是 6 號和 8 號格子:

• 到達 6 號格子有 $3$ 種方法，從 6 到 1 有 $1$ 種方法
• 到達 8 號格子有 $2$ 種方法，從 8 到 1 有 $1$ 種方法
• 那從路徑 6 -> 1 或 8 -> 1 總共就是 $3+2$ 種方法

可以用此規律求出從 0 到 9 的長度 2 有幾種方法。可以得出: 下個狀態($i+1$)就是從上個狀態($i$)加總可以到達第 $j \in [0, 9]$ 號格子的方法數。

// n = 2
5 4 5
6 0 6
5 4 5
x 6 x

AC Code#

Copy

class Solution {
public:
    int mod = 1e9+7;
    vector<int> dp[2];
    void calc(int i)
    {
        /*
        1 2 3
        4 5 6
        7 8 9
        x 0 x
        */
        switch(i)
        {
            case 0:
                dp[1][0] = dp[0][4] + dp[0][6];
                break;
            case 1:
                dp[1][1] = dp[0][6] + dp[0][8];
                break;
            case 2:
                dp[1][2] = dp[0][7] + dp[0][9];
                break;
            case 3:
                dp[1][3] = dp[0][4] + dp[0][8];
                break;
            case 4:
            {
                dp[1][4] = dp[0][0] + dp[0][3];
                dp[1][4] %= mod;
                dp[1][4] += dp[0][9];
                break;
            }
            case 5:
                dp[1][5] = 0;
                break;
            case 6:
                dp[1][6] = dp[0][0] + dp[0][1];
                dp[1][6] %= mod;
                dp[1][6] += dp[0][7];
                break;
            case 7:
                dp[1][7] = dp[0][2] + dp[0][6];
                break;
            case 8:
                dp[1][8] = dp[0][1] + dp[0][3];
                break;
            case 9:
                dp[1][9] = dp[0][2] + dp[0][4];
                break;
        }
        dp[1][i] %= mod;
    }
    int knightDialer(int n)
    {
        dp[0].resize(10, 1);
        dp[1].resize(10, 1);
 
        while(--n)
        {
            for(int i = 0; i < 10; i++)
                calc(i);
            dp[0] = dp[1];
        }
 
        int ans = 0;
        for(int i = 0; i < 10; i++)
        {
            ans += dp[1][i];
            ans %= mod;
        }
 
        return ans;
    }
};

view raw leetcode/935.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

可以將狀態第二個外度壓縮在兩層就好，每次做完在將後蓋前。

賞析#

官方題解竟然有線代的解法