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
-
Method 1: DP O(10 * n^3) AC 1136ms
-
Method 2: dp AC 18ms 93.43%
- use a rotate array to save temp result so we can reduce Memory space from O(12 * N) to O(12 * 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.
