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

我正在尝试在 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?

这是我的代码:输入 1 000 000 000 似乎花费的时间太长

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 

请您参考如下方法:

问题是您的代码将每个递归调用分支为三个新调用。这会导致指数行为。

不过，好消息是大多数调用都是重复的:如果您使用 40 调用 coinProfit，这将级联到:

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 已经有一个名为lru_cache 的内置memoize 函数，可以找到更多信息here .

A final note is that @memoize or other Dynamic programming constructs, are not the solution to all efficiency problems. First of all @memoize can have an impact on side-effects: say your function prints something on stdout, then with @memoize this will have an impact on the number of times something is printed. And secondly, there are problems like the SAT problem where @memoize simply doesn't work at all, because the context itself is exponential (this as far as we know). Such problems are called NP-hard.