找到乘船的最低成本，使用递归和记忆

Question

这就是我的代码：

def O_C(n, prices, start=1, memo=None):
    if start == n:
        return 0
    if memo is None:
        memo = {}
    if start not in memo:
        options = []
        for i in range(start + 1, n + 1):
            options.append(prices(start, i) + O_C(n, prices, i, memo))
        memo[start] = min(options)
    return memo[start]

# O_C stands for Optimal Cost

def make_random_prices(N):
    import random
    prices = {}
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            prices[(i, j)] = random.randint(1, 10*N)
    return prices

prices = make_random_prices(100)
print O_C(100, prices)

我不断收到的错误：

Traceback (most recent call last):
  File "/Users/Ori/Desktop/OneDrive - mail.tau.ac.il/Python/test/recursion.py", line 48, in <module>
    print O_C(100, prices)
  File "/Users/Ori/Desktop/OneDrive - mail.tau.ac.il/Python/test/recursion.py", line 32, in O_C
    options.append(prices(start, i) + O_C(n, prices, i, memo))
TypeError: 'dict' object is not callable

在本网站或任何其他网站上都找不到与此上下文中的此错误相关的任何参考。递归调用可能是错误的？

Answer 1

这个错误解释得很好。在下面的代码行中，

options.append(prices(start, i) + O_C(n, prices, i, memo))

使用 prices[(start, i)] 访问 prices 中由元组 (start, i) 键入的值，而不是尝试调用 prices 通过 prices(start, i)。 prices 这里是 dict，不是 callable。

找到乘船的最低成本，使用递归和记忆

Find lowest cost of a boat ride, Using Recursion and Memoization

python

python-2.7

recursion

grid

memoization