[leetcode/lintcode 题解] 微软面试题:骑士拨号器 算法 刷题解法

DanielZhao 19天前 49


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

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

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

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

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

1≤N≤5000

在线评测地址: https://www.lintcode.com/problem/knight-dialer/?utm_source=sc-xytsq-zq

样例 1:

样例 2:

样例 3:

【题解】

本题采用动态规划的方法,考虑每一步棋子变化的状态,进行统计。我们可以使用滚动数组节省空间。

更多语言代码参见:https://www.jiuzhang.com/solution/knight-dialer/?utm_source=sc-xytsq-zq

最新回复 (0)
返回