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]