我正在尝试在CodeChef上解决此问题：http://www.codechef.com/problems/COINS
但是，当我提交我的代码时，执行时间显然太长，并说时间已经到期。我不确定我的代码是否效率低下（对我而言似乎不是）或我在I / O方面遇到麻烦。有9秒的时间限制，最多可解决10个输入，0
在Byteland，他们有一个非常奇怪的货币体系。
每个Bytelandian金币上都有一个整数。一枚硬币
n可以在银行中兑换成三个硬币：n/2，n/3和n/4。但
这些数字均四舍五入（银行必须获利）。
您也可以以美元出售Bytelandian硬币。找的零钱
比率是1：1。但是您不能购买Bytelandian硬币。
你有一枚金币。美元的最高金额是多少
你可以得到吗？
这是我的代码：输入1000000000000似乎花了太长时间
def coinProfit(n):
a = n/2
b = n/3
c = n/4
if a+b+c > n:
nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
if nextProfit > a+b+c:
return nextProfit
else:
return a+b+c
return n
while True:
try:
n = input()
print(coinProfit(n))
except Exception:
break
最佳答案
问题在于您的代码将每个递归调用分为三个新的调用。这导致指数行为。
不过，最妙的是，大多数调用都是重复的：如果用coinProfit调用40，它将级联为：
coinProfit(40)
- coinProfit(20)
- coinProfit(10)
- coinProfit(6)
- coinProfit(5)
- coinProfit(13)
- coinProfit(10)
您会看到重复了很多工作（在这个小例子中，在
coinProfit上已经两次调用10了）。您可以使用动态编程来解决此问题：存储较早的计算结果，以防止您再次分支到该零件上。
一个人可以实现自己的动态编程，但一个人可以使用
@memoize装饰器自动执行此操作。现在，该功能执行了太多次的大量工作。
import math;
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@memoize
def coinProfit(n):
a = math.floor(n/2)
b = math.floor(n/3)
c = math.floor(n/4)
if a+b+c > n:
nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
if nextProfit > a+b+c:
return nextProfit
else:
return a+b+c
return n
@memoize转换函数，以便：对于该函数，将保留已计算的输出数组。如果对于给定的输入，已经计算出输出，则将其存储在数组中并立即返回。否则，它将根据您的方法定义进行计算，并存储在数组中（以备后用）并返回。正如@steveha指出的那样，python已经有一个名为
memoize的内置lru_cache函数，可以在here中找到更多信息。最后要注意的是，
@memoize或其他动态编程构造并不能解决所有效率问题。首先，@memoize可能会对副作用产生影响：说您的函数在stdout上打印某些内容，然后使用@memoize这将对打印某些内容的次数产生影响。其次，还有诸如SAT问题之类的问题，其中@memoize根本不起作用，因为上下文本身是指数级的（据我们所知）。这种问题称为NP-难。