难度中等
国际象棋中的骑士可以按下图所示进行移动：
这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。 每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。 你能用这种方式拨出多少个不同的号码？ 因为答案可能很大，所以输出答案模 10^9 + 7。
示例 1：
输入：1 输出：10 示例 2：
输入：2 输出：20 示例 3：
输入：3 输出：46
提示： * 1 <= N <= 5000
设置dp[i][n]为：起始点在i上的骑士，跳n步能得到的数字组合。 观察dp[1][4]
由此可得dp[i][n]=dp[{i能跳到的数}][n-1] 观察得出除了4,6有3个后继点，5没有后继点，剩下的都是2个后继点 可将10个起始点划分为5类，每一类的dp[i][n]相等
感觉用这个方法绝壁要超出时间限制
题解部分
f(A,n)=f(B,n-1)+f(C,n-1) f(B,n)=2f(A,n-1) f(C,n)=2f(A,n-1)+f(D,n-1) f(D,n)=2*f(C,n-1) 解释为： 处于状态A中的数字(1,3,7,9)通过一次跳跃要么变成状态B(2,8)，要么变成状态C(4,6) 处于状态B中的数字(2,8)通过一次跳跃有两种方式变成状态A(1,3,7,9) 处于状态C中的数字(4,6)通过一次跳跃有两种方式变成状态A(1,3,7,9)，还有一种方式变成状态D(0) 处于状态D中的数字(0)通过一次跳跃有两种方式变成状态C(4,6)
通过迭代，我们即可求解。
自己的思路前面部分跟大佬的很相似（观察得出10个数字的不同类别），但在实现的部分无从下手，原因是没像大佬一样将多种结果相同的数字抽象成一个状态，并判断状态转移之间消耗的步数，推出各类状态转移公式拿来使用。唉，从例子数字1下手观察到这现象，到最后还是太拘泥于具体实例了，要习惯使用归纳抽象的思想。
