935. Knight Dialer

https://leetcode.com/problems/knight-dialer/

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

.

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makesN-1hops. 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, pressingNdigits total.

How many distinct numbers can you dial in this manner?

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

• Example 1:

Input: 
1
Output: 
10

Example 2:

Input: 
2
Output: 
20

Example 3:

Input: 
3
Output: 
46

Note:

• 1

  <

  = N

  <

  = 5000

Thoughts

初始时可以在手机键盘任意按键上，问按象棋马的走法，跳N-1步后所有可能的跳法的数目。一共N-1步，每步action为从上一步所在按键蹦到另一个可蹦的按键，受限于两个按键是否符合跳马，因此状态中encode哪步落在了哪个按键，dp[i][j]存第i步落在j的总共的可能数。

还有O(lgN)解法，利用了马尔科夫链。

Code

/*
 * @lc app=leetcode id=935 lang=cpp
 *
 * [935] Knight Dialer
 */

// @lc code=start
class Solution {
public:
    int knightDialer(int N) {
        const unsigned int M = 1000000007;
        unordered_map<int, vector<int>> hops{{0, {4, 6}}, {1, {6, 8}},
        {2, {7, 9}}, {3, {4, 8}}, {4, {3, 9, 0}}, 
        {6, {7, 1, 0}}, {7, {2, 6}}, {8, {1, 3}}, {9, {2, 4}}}; 
        vector<vector<int>> dp(2, vector<int>(10, 0));
        for (int i = 0; i <= 9; ++i) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j <= 9; ++j) dp[i % 2][j] = 0;
            for (int j = 0; j <= 9; ++j) {
                for (const auto p : hops[j]) {
                    dp[i % 2][j] += dp[(i - 1) % 2][p];
                    dp[i % 2][j] %= M;
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= 9; ++i) {
            res += dp[(N - 1) % 2][i];
            res %= M;
        }
        return res;
    }
};
// @lc code=end

Analysis

时间复杂度O(N).