> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/zou-ge/knight-dialer.md).

# 935. Knight Dialer

> A chess knight can move as indicated in the chess diagram below:
>
> ![](https://assets.leetcode.com/uploads/2018/10/12/knight.png) . ![](https://assets.leetcode.com/uploads/2018/10/30/keypad.png)
>
> 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:**
>
> ```
> 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

```cpp
/*
 * @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).