回溯算法尝试
在leetcode上面看到跳楼梯的问题，自已想尝试用回溯算法将所有可能的情况全部呈现出来，代码如下（死循环）：def test():
ans = []
index = 0
def go(index, step):
index += step
return index
def back(index, step):
index -= step
return index
def add_solution(res):
ans.append(res)
return ans
def main(list_ = , res = []):
print(index)
for step in range(1, list_ + 1):
if index < len(list_) - 1:
res.append(step)
go(index, step)
print(index, res)
test(list_, res)
elif index == len(list_) - 1:
add_solution(res)
back(index, step)
print(index)
break
elif index > len(list_) - 1:
break
res = res[:-1]
print(res, ans)
main()
其中list_的index为楼梯的层数，list_为当前楼梯可行进的最大步数，希望输出ans为所有爬楼的可能走法；
在main中会出现死循环，原因是go和back函数并没有想我想象中的修改index的值，希望大佬能教教我这里是什么原理；
如果能教教我回溯算法就更好了啊哈哈哈{:5_109:}
try this:def test():
ans = []
index = 0
def go(index, step):
nonlocal index
index += step
def back(index, step):
nonlocal index
index -= step
def add_solution(res):
ans.append(res)
return ans
def main(list_ = , res = []):
print(index)
for step in range(1, list_ + 1):
if index < len(list_) - 1:
res.append(step)
go(step)
print(index, res)
test(list_, res)
elif index == len(list_) - 1:
add_solution(res)
back(step)
print(index)
break
elif index > len(list_) - 1:
break
res = res[:-1]
print(res, ans)
main()这个是变量作用域和不可变对象的问题。
PS：建议楼主先打好基础，再去力扣做题哦
页:
[1]