leetcode 935

问题

A chess knight can move as indicated in the chess diagram below:

img . img

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

1
2
Input: 1
Output: 10

Example 2:

1
2
Input: 2
Output: 20

Example 3:

1
2
Input: 3
Output: 46

Note:

  • 1 <= N <= 5000

分析

思路1: 动态规划

思路2: 使用无向图的性质 https://leetcode.com/problems/knight-dialer/discuss/189252/O(logN)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int knightDialer(int N) {
        vector<vector<int>> prevTable = {
            {4,6},
            {6,8},
            {7,9},
            {4,8},
            {3,9,0},
            {},
            {1,7,0},
            {2,6},
            {1,3},
            {2,4}
        };
        vector<int> dp(10, 1), dp2;
        for (int i = 2; i <= N; ++i) {
            dp2 = dp;
            for (int j = 0; j < 10; ++j) {
                dp[j] = 0;
                for (int y: prevTable[j]) {
                    dp[j] = (dp[j]+dp2[y])%(1000000007);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 10; ++i) {
            ans = (ans + dp[i])%1000000007;
        }
        return ans;
    }
};