在超出内存限制的Lintcode python解决方案中绘制围栏

Question

我正在用Python解决lintcode中的paint fence问题。在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。你知道吗