問題
某樓梯有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步
效果圖
