原题链接在这里：

题目：

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: 1Output: 10

Example 2:

Input: 2Output: 20

Example 3:

Input: 3Output: 46

Note:

• 1 <= N <= 5000

题解：

The question asks distinct numbers could dial.

It is actually the sum of ways jump ending at each cell.

Cell 1 could jump to cell 6 and 8. Thus accumlate the current ways count to next ways at 6 and 8.

Eventually, get all the sum.

Time Complexity: O(N).

Space: O(1).

AC Java: 

1 class Solution { 2     public int knightDialer(int N) { 3         if(N == 0){ 4             return 0; 5         } 6          7         if(N == 1){ 8             return 10; 9         }10         11         int M = 1000000007;12         long [] cur = new long[10];13         Arrays.fill(cur, 1);14         for(int k = 2; k<=N; k++){15             long [] next = new long[10];16 17             next[1] = (cur[6]+cur[8])%M;18             next[2] = (cur[7]+cur[9])%M;19             next[3] = (cur[4]+cur[8])%M;20             next[4] = (cur[3]+cur[9]+cur[0])%M;21             next[5] = 0;22             next[6] = (cur[1]+cur[7]+cur[0])%M;23             next[7] = (cur[2]+cur[6])%M;24             next[8] = (cur[1]+cur[3])%M;25             next[9] = (cur[2]+cur[4])%M;26             next[0] = (cur[4]+cur[6])%M;27             28             cur = next;29         }30         31         long res = 0;32         for(int i = 0; i<10; i++){33             res = (res + cur[i]) % M;34         }35         return (int)res;36     }37 }