# 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`**.

{% hint style="info" %}
首先找出每個鍵的前一步可以在哪些鍵上，譬如0的前一步可以在4或6上，1的前一步可以在6或8上，以此類推建立一個可以在過程中重複查找的表。這題一開始邏輯寫對了，但因為疏忽了overflow的問題，所以OJ卡了很久，尤其是要注意最後算數列裡的數字加總。
{% endhint %}

```cpp
static const int MOD = 1000000007;
// Dynamic Programming
int knightDialer(int N) { // time: O(N); space: O(1)
    vector<vector<int> > neighbors({ {4,6}, {6,8}, {7,9}, {4,8}, {0,3,9}, {}, {0,1,7}, {2,6}, {1,3}, {2,4} });
    vector<long> count(10, 1);
    for (int i = 0; i < N - 1; ++i) {
        vector<long> tmp(10, 0);
        for (int j = 0; j < 10; ++j) { // position
            for (int k : neighbors[j]) { // neighbor
                tmp[j] = (tmp[j] + count[k]) % MOD;
            }
        }
        count = tmp;
    }
    return accumulate(count.begin(), count.end(), (long)0) % MOD;
}
```

{% hint style="info" %}
還有O(logN)的解，理解後再補上。
{% endhint %}