Open grandyang opened 5 years ago
看了看博客, 用两个大小为10的数组就可以了, 不需要N个, 做完一次swap一下就可以了
这个题目用矩阵相乘performance 是 O(log(N)), 要比一步步的算dp快很多。据说这是google的一道面试题, 但是现在已经上黑名单了,因为大家都知道了。
这个题目用矩阵相乘performance 是 O(log(N)), 要比一步步的算dp快很多。据说这是google的一道面试题, 但是现在已经上黑名单了,因为大家都知道了。
求贴代码
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:
Example 2:
Example 3:
Note:
1 <= N <= 5000
这道题说是有一种骑士拨号器,在一个电话拨号盘上跳跃,其跳跃方式是跟国际象棋中的一样,不会国际象棋的童鞋可以将其当作中国象棋中的马,马走日象飞田。这个骑士可以放在 10 个数字键上的任意一个,但其跳到的下一个位置却要符合其在国际象棋中的规则,也就是走日。现在给了一个整数N,说是该骑士可以跳N次,问能拨出多个不同的号码,并且提示了结果要对一个超大数字取余。看到这里,对于各位刷题老司机来说,肯定能反应过来要用动态规划 Dynamic Programming 了吧,因为数字可能巨大无比,强行暴力递归破解可能会爆栈。这里使用一个二维数组 dp,其中 dp[i][j] 表示骑士第i次跳到数字j时组成的不同号码的个数,那么最终所求的就是将 dp[N-1][j] 累加起来,j的范围是0到9。接下来看状态转移方程怎么写,当骑士在第i次跳到数字j时,考虑其第 i-1 次是在哪个位置,可能有多种情况,先来分析拨号键盘的结构,找出从每个数字能到达的下一个位置,可得如下关系:
0 -> 4, 6
1 -> 6, 8
2 -> 7, 9
3 -> 4, 8
4 -> 3, 9, 0
5 ->
6 -> 1, 7, 0
7 -> 2, 6
8 -> 1, 3
9 -> 4, 2
可以发现,除了数字5之外,每个数字都可以跳到其他位置,其中4和6可以跳到三个不同位置,其他都只能取两个位置。反过来想,可以去的位置,就表示也可能从该位置回来,所以根据当前的位置j,就可以在数组中找到上一次骑士所在的位置,并将其的 dp 值累加上即可,这就是状态转移的方法,由于第一步是把骑士放到任意一个数字上,就要初始化 dp[0][j] 为1,然后进行状态转移就行了,记得每次累加之后要对超大数取余,最后将 dp[N-1][j] 累加起来的时候,也要对超大数取余,参见代码如下:
解法一:
我们也可以用递归+记忆数组的方式来写,整体思路和迭代的方法并没有什么区别,之前类似的题目也不少,就不多解释了,可以对照上面的讲解和代码来理解,参见代码如下:
解法二:
Github 同步地址:
https://github.com/grandyang/leetcode/issues/935
类似题目:
Letter Combinations of a Phone Number
参考资料:
https://leetcode.com/problems/knight-dialer/
https://leetcode.com/problems/knight-dialer/discuss/189265/Concise-Java-DP-Solution
https://leetcode.com/problems/knight-dialer/discuss/189271/Java-Top-Down-Memo-DP-O(N)
https://leetcode.com/problems/knight-dialer/discuss/190787/How-to-solve-this-problem-explained-for-noobs!!!
LeetCode All in One 题目讲解汇总(持续更新中...)