python – 优化算法
发布时间:2020-12-16 22:49:18 所属栏目:Python 来源:网络整理
导读:问题: 在给定的标准拨号盘上,跳跃N次可以产生的唯一数字的数量是多少,当你跳跃时,你必须像骑士棋子一样移动.您也无法登陆X之类的任何无效值,但您可以通过它们. 拨号器: 1 2 34 5 67 8 9X 0 X 与此非常相似 Generate 10-digit number using a phone keypad
问题: 在给定的标准拨号盘上,跳跃N次可以产生的唯一数字的数量是多少,当你跳跃时,你必须像骑士棋子一样移动.您也无法登陆X之类的任何无效值,但您可以通过它们. 拨号器:
与此非常相似 Generate 10-digit number using a phone keypad 到目前为止我有什么但是疯狂的慢(Python 2.7)
我猜测最简单的优化方法是进行某种记忆,但我无法弄清楚如何使用问题约束. 最佳答案
设K(k,n)是从密钥k开始的长度为n的唯一数的个数.然后,K(k,n 1)= sum(K(i,n)),其中i在可以从键k跳转到的键的范围内.
这可以使用动态编程有效地计算;这是一种占用O(n)时间和O(1)空间的方法:
更快:可以在log(n)时间和O(1)空间中计算答案.设M是10乘10矩阵,如果可以从i跳到j,则M [i,j] = 1,否则为0.然后求和(M ^ n * ones(10,1))就是答案.可以通过在log(n)时间中求平方来使用取幂来计算矩阵功率.这是使用numpy的一些代码:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |