【DP】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

解题思路：

根据骑士的移动规则，可以得到从0~9这10个位置移动到的下一个位置： next_move = [[4,6],[6,8],[7,9],[4,8],[0,3,9],[],[0,1,7],[2,6],[1,3],[2,4]] 其中，next_move[i] 表示从位置 i 能跳到的下一个位置。

对于跳动 N 次，我们可以根据第 N-1 次的结果递推得到。因此，我们只需要一个大小为 10 的数组，来记录跳了 i 次，0~9 这 10 个位置跳到的次数。在进行第 i+1 次递推时，对于 0~9 每个位置，根据 next_move 找到对应的下一跳的位置，然后统计跳到的每个新位置的次数。最后，将大小为 10 的数组中的结果求和，再除以 10**9+7 就是最后的答案。

注意：在实现时，因为只要保存上一次的数组结果，所以不需要 dp[N] 大小的空间来记录前 N 次的所有结果。只需要两个变量赋值即可。

Python3 实现：

class Solution:
    def knightDialer(self, N: int) -> int:
        res = [1] * 10  # 每个位置出现的次数
        next_move = [[4,6],[6,8],[7,9],[4,8],[0,3,9],[],[0,1,7],[2,6],[1,3],[2,4]]
        i = 1
        while i < N:
            res2 = [0] * 10
            for k, v in enumerate(res):
                for j in next_move[k]:  # 对于跳到的下一个位置，更新出现的次数
                    res2[j] += v
            res = res2  # 更新结果
            i += 1
        return sum(res) % (10**9 +7)  # 不要忘记取余