本文實例講述了Python使用回溯法子集樹模板解決爬樓梯問題。分享給大家供大家參考，具體如下：
問題
某樓梯有n層臺階，每步只能走1級臺階，或2級臺階。從下向上爬樓梯，有多少種爬法？
分析
這個問題之前用分治法解決過。但是，這里我要用回溯法子集樹模板解決它。
祭出元素-狀態空間分析大法：每一步是一個元素，可走的步數[1,2]就是其狀態空間。不難看出，元素不固定，狀態空間固定。
直接上代碼。
代碼
'''爬樓梯'''n = 7 # 樓梯階數x = [] # 一個解（長度不固定，1-2數組，表示該步走的臺階數）X = [] # 一組解# 沖突檢測def conflict(k): global n, x, X # 部分解步的步數之和超過總臺階數 if sum(x[:k+1]) > n: return True return False # 無沖突# 回溯法（遞歸版本）def climb_stairs(k): # 走第k步 global n, x, X if sum(x) == n: # 已走的所有步數之和等于樓梯總臺階數 print(x) #X.append(x[:]) # 保存（一個解） else: for i in [1, 2]: # 第k步這個元素的狀態空間為[1,2] x.append(i) if not conflict(k): # 剪枝 climb_stairs(k+1) x.pop() # 回溯# 測試climb_stairs(0) # 走第0步
效果圖
希望本文所述對大家Python程序設計有所幫助。
新聞熱點
疑難解答
