我的短递归函数执行时间太长，我如何优化我

Question

我试图在CodeChef上解决这个问题：http://www.codechef.com/problems/COINS

但是当我提交我的代码时，它显然需要很长时间来执行，并且说时间已经过期。我不确定我的代码是低效的（我觉得不是这样），还是I/O有问题。有9秒的时间限制，可以解决最多10个输入，0<；=n<；=1 000 000 000。在

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

这是我的代码：输入1000000000似乎花费了太长的时间

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

Answer 1

您可以通过将结果存储在某种类型的cache中来优化程序。因此，如果结果存在于cache中，则无需执行计算，否则计算并将值放入cache。这样可以避免计算已计算的值。E、 g

cache = {0: 0}


def coinProfit(num):
    if num in cache:
        return cache[num]
    else:
        a = num / 2
        b = num / 3
        c = num / 4
        tmp = coinProfit(c) + coinProfit(b) + coinProfit(a)
        cache[num] = max(num, tmp)
        return cache[num]


while True:
    try:
        print coinProfit(int(raw_input()))
    except:
        break