935. 骑士拨号器
国际象棋中的骑士可以按下图所示进行移动：
.
这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。
每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下
N 位数字。你能用这种方式拨出多少个不同的号码？
因为答案可能很大，所以输出答案模
10^9 + 7。示例 1：
输入：1 输出：10
示例 2：
输入：2 输出：20
示例 3：
输入：3 输出：46
提示：
1 <= N <= 5000
法1 动态规划
思路
dp[i][j] 为长度为 i 的，以 j 结尾的有多少种可能。
dp[i][0] = dp[i-1][4] + dp[i-1][6]
dp[i][1] = dp[i-1][8] + dp[i-1][6]
。。。。
可以发现，当前轮之和上一轮有关系，所以，只需要保存上一轮的状态即可，因而采用一维度数组。
同 1220. 统计元音字母序列的数目 ， 当前的数量由上一个决定。
题解
class Solution: def knightDialer(self, n: int) -> int: MOD = 10 ** 9 + 7 # 初始都设定为 1， 当n > 1 时，5 应该为0 ，因为没有元素可以到达5 dp = [1] * 10 for i in range(1, n): dp = [ (dp[4] + dp[6]) % MOD, (dp[6] + dp[8]) % MOD, (dp[7] + dp[9]) % MOD, (dp[4] + dp[8]) % MOD, (dp[0] + dp[9] + dp[3]) % MOD, 0, (dp[0] + dp[1] + dp[7]) % MOD, (dp[2] + dp[6]) % MOD, (dp[1] + dp[3]) % MOD, (dp[2] + dp[4]) % MOD ] return sum(dp) % MOD