python - Lintcode 中的油漆栅栏 - 超出内存限制的 python 解决方案

Question

我正在解决 paint fence Python 的 lintcode 问题。在python代码中，我定义了一个只有4个元素的列表，并运行循环根据递归方程更新最后三个元素，但提交失败并告诉我“超出内存限制”。这是代码:

class Solution:
    # @param {int} n non-negative integer, n posts
    # @param {int} k non-negative integer, k colors
    # @return {int} an integer, the total number of ways
    def numWays(self, n, k):
        # Write your code here
        table = [0, k, k*k, 0]

        if n <= 2:
            return table[n]

        # recurrence equation
        # table[posts] = (color - 1) * (table[posts - 1] + table[posts - 2])
        for i in range(3, n + 1):
            table[3] = (k - 1) * (table[1] + table[2])
            table[1], table[2] = table[2], table[3]

        return table[3]

我没有发现这段代码有任何问题。有人可以帮我解决一下吗？

Answer 1

使用xrange而不是range。请参阅xrange了解更多信息。