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

解题思路：很明显的动态规划的场景。首先我们可以维护如下的一个映射字典:key为到达的数字，value为可以由哪些数字经过一次跳跃到达key的数字。接下来假设dp[i][j] 为经过跳跃i次并且最后一次跳跃的终点是j，那么有dp[i][j] = dp[i-1][dic[j][0]] + dp[i-1][dic[j][1]] + ... dp[i-1][dic[j][n]]。最终的结果就是dp[N][0] + dp[N][1] + ... dp[N][9]。后来经过测试发现，这种解法会超时，因为题目约定了N最大是5000，因此可以事先计算出1~5000的所有结果缓存起来。

　　　　 dic[1] = [6,8]

        dic[2] = [7,9]

        dic[3] = [4,8]

        dic[4] = [3,9,0]

        dic[5] = []

        dic[6] = [1,7,0]

        dic[7] = [2,6]

        dic[8] = [1,3]

        dic[9] = [2,4]

        dic[0] = [4,6]

代码如下：

class Solution(object):

    res = []

    def knightDialer(self, N):

        """

        :type N: int

        :rtype: int

        """

        if len(self.res) != 0:

            return self.res[N-1]

        dic = {}

        dic[1] = [6,8]

        dic[2] = [7,9]

        dic[3] = [4,8]

        dic[4] = [3,9,0]

        dic[5] = []

        dic[6] = [1,7,0]

        dic[7] = [2,6]

        dic[8] = [1,3]

        dic[9] = [2,4]

        dic[0] = [4,6]

        dp = []

        for i in range(5001):

            if i == 0:

                tl = [1] * 10

            else:

                tl = [0] * 10

            dp.append(tl)

        for i in range(5001):

            for j in range(10):

                for k in dic[j]:

                    dp[i][j] += dp[i-1][k]

        for i in range(5001):

            self.res.append(sum(dp[i]) % (pow(10,9) + 7))

        return self.res[N-1]

巴特西

【leetcode】935. Knight Dialer

最新文章

热门文章