Python中的道路計算（遞歸）

Question

我需要計算從n到0的道路數量，但我的代碼似乎適用於某些情況，有些則不適用。

編輯： 當我嘗試執行：道路（7，2,3） 它表明：

線95是在末端

Traceback (most recent call last): 
    File "python", line 102, in <module> 
    File "python", line 95, in roads 
    File "python", line 95, in roads 
    File "python", line 95, in roads 
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int' 

---

def jumps(n, j): 

    if n == 0: 
     return True 
    elif n<0: 
     return False 
    else: 
     if n<j: 
      return False 
     elif n==j: 
      return True 
     elif n>j: 
      if n%j ==0: 
       return True 
      else: 
       return False 

def roads(n, short_jump, long_jump, memo=None): 

    if memo == None: 
     memo = {} 

    if n not in memo: 
     if n==0: 
      memo[n] = 1 
      return memo[n] 
     elif n<0: 
      memo[n] = 0 
      return memo[n] 
     else: 
      sum_hmrm = 0 

      a = jumps(n, short_jump) 
      b = jumps(n, long_jump) 
      c = n-long_jump 
      d = n-short_jump 

      if a == True: 
       sum_hmrm += 1 
      if b == True: 
       sum_hmrm += 1 

      sum_hmrm += (roads(c, short_jump, long_jump, memo) + roads(d, short_jump, long_jump, memo)) 

      memo[n] = sum_hmrm 
      return memo[n] 

Answer 1

遞歸部分

這個問題與你如何做記憶有關。您的代碼的主體是在if n not in memo的條件。但是，如果不滿足這個條件，你什麼也不做。這意味着如果您嘗試重新計算已經評估的值，則返回None而不是緩存的值。

我想你想刪除你的縮進return線，並添加一個在函數的結尾是不是if語句中：

if n not in memo: 
    if n==0: 
     memo[n] = 1 # remove return after this line 
    elif n<0: 
     memo[n] = 0 # and here 
    else: 
     sum_hmrm = 0 

     a = jumps(n, short_jump) 
     b = jumps(n, long_jump) 
     c = n-long_jump 
     d = n-short_jump 

     if a == True: 
      sum_hmrm += 1 
     if b == True: 
      sum_hmrm += 1 

     sum_hmrm += (roads(c, short_jump, long_jump, memo) + roads(d, short_jump, long_jump, memo)) 

     memo[n] = sum_hmrm # the one after this line can just be unindented 

return memo[n]