回溯算法尝试

jody970214

在leetcode上面看到跳楼梯的问题，自已想尝试用回溯算法将所有可能的情况全部呈现出来，代码如下（死循环）：

1. def test():
   
2.    
   
3.     ans = []
   
4.     index = 0
   
5. 
   
6.     def go(index, step):
   
7.         index += step
   
8.         return index
   
9.    
   
10.     def back(index, step):
    
11.         index -= step
    
12.         return index
    
13.    
    
14.     def add_solution(res):
    
15.         ans.append(res)
    
16.         return ans
    
17.    
    
18.     def main(list_ = [2,3,1,4], res = []):
    
19.         print(index)
    
20.         for step in range(1, list_[index] + 1):
    
21.             if index < len(list_) - 1:
    
22.                 res.append(step)
    
23.                 go(index, step)
    
24.                 print(index, res)
    
25.                 test(list_, res)
    
26.             elif index == len(list_) - 1:
    
27.                 add_solution(res)
    
28.                 back(index, step)
    
29.                 print(index)
    
30.                 break
    
31.             elif index > len(list_) - 1:
    
32.                 break
    
33.         res = res[:-1]
    
34.         print(res, ans)
    
35.             
    
36.     main()

复制代码

其中list_的index为楼梯的层数，list_[index]为当前楼梯可行进的最大步数，希望输出ans为所有爬楼的可能走法；
在main中会出现死循环，原因是go和back函数并没有想我想象中的修改index的值，希望大佬能教教我这里是什么原理；
如果能教教我回溯算法就更好了啊哈哈哈

永恒的蓝色梦想

try this:

1. def test():
   
2.    
   
3.     ans = []
   
4.     index = 0
   
5. 
   
6.     def go(index, step):
   
7.         nonlocal index
   
8.         index += step
   
9.    
   
10.     def back(index, step):
    
11.         nonlocal index
    
12.         index -= step
    
13.    
    
14.     def add_solution(res):
    
15.         ans.append(res)
    
16.         return ans
    
17.    
    
18.     def main(list_ = [2,3,1,4], res = []):
    
19.         print(index)
    
20.         for step in range(1, list_[index] + 1):
    
21.             if index < len(list_) - 1:
    
22.                 res.append(step)
    
23.                 go(step)
    
24.                 print(index, res)
    
25.                 test(list_, res)
    
26.             elif index == len(list_) - 1:
    
27.                 add_solution(res)
    
28.                 back(step)
    
29.                 print(index)
    
30.                 break
    
31.             elif index > len(list_) - 1:
    
32.                 break
    
33.         res = res[:-1]
    
34.         print(res, ans)
    
35.             
    
36.     main()

复制代码

这个是变量作用域和不可变对象的问题。

PS：建议楼主先打好基础，再去力扣做题哦