[Swift Weekly Contest 109]LeetCode935. 骑士拨号器 | 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 hop

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: 1Output: 10 

Example 2:

input: 2Output: 20 

Example 3:

input: 3Output: 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..<1020             {21                 ndp[j] %= mod22             }23             dp = ndp24         }25         var ret:Int64 = 026         for i in 0..<1027         {28             ret += dp[i]29         }30         return Int(ret % mod)31     }32 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 109]LeetCode935. 骑士拨号器 | Knight Dialer全部内容，希望文章能够帮你解决[Swift Weekly Contest 109]LeetCode935. 骑士拨号器 | Knight Dialer所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。