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 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

move_to	11643	3	3
<method 'items' of 'dict' objects>	1	0	0
<built-in method builtins.__build_class__>	1	0	0
<built-in method builtins.len>	6576	0	0
<built-in method builtins.print>	1	0	0
<module>	1	3	0
Solution	1	0	0
knightDialer	1	3	0

  class Solution(object):
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        def move_to(now_number, n):
            key = '{}|{}'.format(now_number,n)

            if n == 1:
                if move_to_cache.get(key):
                    return move_to_cache.get(key)
                move_to_cache[key] = len(preview_numbers_of[now_number])
                return len(preview_numbers_of[now_number])
            else:
                if move_to_cache.get(key):
                    return move_to_cache.get(key)
                now = 0
                for number in preview_numbers_of[now_number]:
                    now += move_to(number, n-1)

                move_to_cache[key] = now
                return now

        preview_numbers_of = {1: [6, 8],
                              2: [7, 9],
                              3: [4, 8],
                              4: [3, 9, 0],
                              6: [1, 7, 0],
                              7: [2, 6],
                              8: [1, 3],
                              9: [2, 4],
                              0: [4, 6]}
        move_to_cache = {}
        if N == 1:
            return 10
        else:
            sum_num = 0
            for k, v in preview_numbers_of.items():
                sum_num += move_to(k, N-1)
            return sum_num


if __name__ == '__main__':
    s = Solution()
    print(s.knightDialer(N=10))  

<method 'format' of 'str' objects>	169	0	0
<method 'get' of 'dict' objects>	257	0	0
<method 'items' of 'dict' objects>	1	0	0
<built-in method builtins.__build_class__>	1	0	0
<built-in method builtins.len>	18	0	0
<built-in method builtins.print>	1	0	0
<module>	1	0	0
move_to	169	0	0
Solution	1	0	0
knightDialer	1	0	0

    def knightDialer(self, N):
        preview_numbers_of = [ [4, 6],  [6, 8],  [7, 9],  [4, 8], [0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3],
              [2, 4]]
        dp = [[0] * 10 for _ in range(N)]
        mod = 10 ** 9 + 7
        for i in range(10): dp[0][i] = 1

        for i in range(1, N):
            for j in range(10):
                for number in preview_numbers_of[j]:
                    dp[i][j] += dp[i - 1][number]
                dp[i][j] %= mod

        return sum(dp[N - 1]) % mod

class Solution(object):
    def knightDialer(self, N):
        MOD = 10**9 + 7
        moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],
                     [1,7,0],[2,6],[1,3],[2,4]]

        dp = [1] * 10
        for hops in xrange(N-1):
            dp2 = [0] * 10
            for node, count in enumerate(dp):
                for nei in moves[node]:
                    dp2[nei] += count
                    dp2[nei] %= MOD
            dp = dp2
        return sum(dp) % MOD

from type import List
class Book:
    def __init__(self):
        ...

class BookService:
    def __init__(self):
       ...
       ...
    
    def get_books_by_type(type: str) -> List(Book):
       ...