难度：★★★★☆
类型：数组
方法：动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

国际象棋中的骑士可以按下图所示进行移动：

这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。

每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。

你能用这种方式拨出多少个不同的号码？

因为答案可能很大，所以输出答案模 10^9 + 7。

示例 1：

输入：1
输出：10

示例 2：

输入：2
输出：20

示例 3：

输入：3
输出：46

提示：

1 <= N <= 5000
通过次数4,818提交次数10,262

解答

我们用动态规划来解决。不过这里有一个可以利用的条件，即每一跳之间的关系时确定的，既然规则限定，我们就可以把规则保存在下面一个表中：

        moves = [[4, 6],
                 [6, 8],
                 [7, 9],
                 [4, 8],
                 [3, 9, 0],
                 [],
                 [1, 7, 0],
                 [2, 6],
                 [1, 3],
                 [2, 4]]

move[i]表示i位置的前一跳的所有可能的数字的列表。

【数组定义】

定义数组dp，长度为10，dp[i]表示以i位置结尾的所有路径的可能性。

【初始状态】

因为至少从1开始，以任意位置结尾的路径的长度都是1，可能性也都是1，印刻全部填充1.

【递推公式】

我们想要知道以i结尾的路径有多少种可能，就需要知道到达i的上一跳位置j是什么，以及以上一跳位置j结尾的路径有多少种可能。获取上一跳位置可以通过查表，获取上一跳位置的可能路径总和又需要上一步的dp数组。为了不破坏dp数组，我们每一跳开始时都准备一个新数组current_dp，在这一跳计算完成后更新dp数组。

由于上一跳可能有多个位置选择，因此需要将各位置的结果相加，作为当前dp[i]的数值。

最后，我们将所有10个位置结尾的路径数相加，即为所有可能结果。

class Solution(object):
    def knightDialer(self, N):
        moves = [[4, 6],
                 [6, 8],
                 [7, 9],
                 [4, 8],
                 [3, 9, 0],
                 [],
                 [1, 7, 0],
                 [2, 6],
                 [1, 3],
                 [2, 4]]

        dp = [1] * 10
        for _ in range(N-1):
            current_dp = [0] * 10
            for number, count in enumerate(dp):
                for nei in moves[number]:
                    current_dp[nei] += count
            dp = current_dp
        return sum(dp) % (10**9 + 7)


s = Solution()
print(s.knightDialer(2))

如果想知道路径到底有哪些，可以参考下面的代码：

class Solution(object):
    def knightDialer(self, N):
        moves = [[4, 6],
                 [6, 8],
                 [7, 9],
                 [4, 8],
                 [3, 9, 0],
                 [],
                 [1, 7, 0],
                 [2, 6],
                 [1, 3],
                 [2, 4]]
        res = [[[i]] for i in range(10)]

        dp = [1] * 10
        for _ in range(N-1):
            current_dp = [0] * 10
            current_res = [[] for _ in range(10)]

            for next_step, count in enumerate(dp):
                for prev_step in moves[next_step]:

                    current_dp[prev_step] += count

                    for path in res[prev_step]:
                        current_res[next_step].append(path + [next_step])

            dp = current_dp
            res = current_res

        res_ = []
        for r in res:
            for path in r:
                res_.append(path)
        print(res_)
        print(len(res_))

        return sum(dp) % (10**9 + 7)


s = Solution()
print(s.knightDialer(2))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析