Question:

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

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

Solution:

  • Method 1: DP O(10 * n^3) AC 1136ms Imgur

  • Method 2: dp AC 18ms 93.43%

    1. use a rotate array to save temp result so we can reduce Memory space from O(12 * N) to O(12 * 2)
    2. If we can change the way we calculate for the knight moving, we just can use a 1-D array and we don’t need to to any validation process. Imgur

Reference

  1. 花花酱 LeetCode 935. Knight Dialer