[Swift Weekly Contest 109]LeetCode935. 骑士拨号器 | Knight D

发布时间：2020-12-14 05:10:22 所属栏目：百科来源：网络整理

导读：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 an

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

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

?.? ? ? ? ? ?

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

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

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

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

示例 1：

输入：1
输出：10

示例 2：

输入：2
输出：20

示例 3：

输入：3
输出：46

提示：

1 <= N <= 5000

284ms

 1 class Solution {
 2     func knightDialer(_ N: Int) -> Int {
 3         var N = N
 4         var mod:Int64 = 1000000007
 5         N -= 1
 6         var dp:[Int64] = [Int64](repeating: 1,count: 10)
 7         for i in 0..<N
 8         {
 9             var ndp:[Int64] = [Int64](repeating: 0,count: 10)
10             ndp[0] = dp[4] + dp[6]
11             ndp[1] = dp[6] + dp[8]
12             ndp[2] = dp[7] + dp[9]
13             ndp[3] = dp[4] + dp[8]
14             ndp[4] = dp[3] + dp[9] + dp[0]
15             ndp[6] = dp[1] + dp[7] + dp[0]
16             ndp[8] = dp[1] + dp[3]
17             ndp[7] = dp[2] + dp[6]
18             ndp[9] = dp[2] + dp[4]
19             for j in 0..<10
20             {
21                 ndp[j] %= mod
22             }
23             dp = ndp
24         }
25         var ret:Int64 = 0
26         for i in 0..<10
27         {
28             ret += dp[i]
29         }
30         return Int(ret % mod)
31     }
32 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!