LeetCode [935] Knight Dialer

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/* 68 79 48 039 017 26 13 24 46 */ typedef long long ll; class Solution { const int X = 1000000007; public: int knightDialer(int N) { if (N==1) return 10; vector<vector<ll>> dp(N+1, vector<ll>(10, 1));//dp[i][j] is the i-length #number ends at j for(int i = 2; i<=N; ++i){ dp[i][0] = (dp[i-1][4] + dp[i-1][6])%X; dp[i][1] = (dp[i-1][6] + dp[i-1][8])%X; dp[i][2] = (dp[i-1][7] + dp[i-1][9])%X; dp[i][3] = (dp[i-1][4] + dp[i-1][8])%X; dp[i][4] = (dp[i-1][3] + dp[i-1][9] + dp[i-1][0])%X; dp[i][6] = (dp[i-1][1] + dp[i-1][7] + dp[i-1][0])%X; dp[i][7] = (dp[i-1][2] + dp[i-1][6])%X; dp[i][8] = (dp[i-1][1] + dp[i-1][3])%X; dp[i][9] = (dp[i-1][2] + dp[i-1][4])%X; } int ret = 0; for(int j=0; j<=9; ++j){ if (j!=5) ret = (ret + dp[N][j])%X; } return ret%X; } };