Lintcodeのペイントフェンス - メモリ制限を超えるPythonソリューション

Question

lintcodeのPythonでの問題を解決しました。 Pythonコードでは、4つの要素しかないリストを定義し、繰り返し式に従って最後の3つの要素を更新するためにループを実行しましたが、送信が失敗し、「メモリ制限を超過しました」と言われました。コードは次のとおりです。

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

rangeの代わりにxrangeを使用してください。詳細は、xrangeを参照してください。