算法训练之回溯法

痛定思痛。 2022-09-12 10:46 196阅读 0赞

## 什么是回溯法 ##

## 题目1 ##

已知完成一个简单的工作需要1天，中等难度，需要2天，困难需要4天，如果未来有n个工作日，请返回所以可能的任务排列数。

如 输入：3  
输出:3 这里3表示3种方案，\{\[1,1,1\], \[1.2\],\[2,1\]\}

## 解法1 ##

采用递归的方法输出最终的方案数：

def solution(n,count):
    	if (n===0):
    		count +=1
    	if (n>=4):
    		solution(n-4)
    	if (n>=2):
    		solution(n-2)
    	if (n>=1):
    		solution(n-1)

## 解法2 ##

使用回溯法解决

def climb_stairs(k): # 走第k步
      global n, temp, results
      if sum(temp) == n: # 已走的所有步数之和等于楼梯总台阶数
        results.append(temp)
        print(temp)
      else:
        for i in [1, 2,4]: # 第k步这个元素的状态空间为[1,2，4]
          temp.append(i)
          if sum(temp)<=n: # 剪枝
            # print(x)
            climb_stairs(k+1)
          temp.pop()       # 回溯
    # 测试
    if __name__ == "__main__":
    	'''爬楼梯'''
    	n = 3 # 楼梯阶数
    	temp = []  # 一个解（长度不固定，1-2数组，表示该步走的台阶数）
    	results = []  # 一组解
    	climb_stairs(0) # 走第0步
    	print(len(results))

输出（n=3时）：  
![在这里插入图片描述][d6c663f33626485e9ee19ad70b70fdd9.png]

## 题目2 ##

问题：n阶楼梯，每次只能走一步或两步，输出所有方案  
LeetCode有这道题, 求解思路也是一样的，换汤不换药

def climb_stairs(k): # 走第k步
      global n, temp, results
      if sum(temp) == n: # 已走的所有步数之和等于楼梯总台阶数
        results.append(temp)
        print(temp)
      else:
        for i in [1, 2]: # 第k步这个元素的状态空间为[1,2]
          temp.append(i)
          if sum(temp)<=n: # 剪枝
            # print(x)
            climb_stairs(k+1)
          temp.pop()       # 回溯
    # 测试
    if __name__ == "__main__":
    	'''爬楼梯'''
    	n = 3 # 楼梯阶数
    	temp = []  # 一个解（长度不固定，1-2数组，表示该步走的台阶数）
    	results = []  # 一组解
    	climb_stairs(0) # 走第0步
    	print(len(results))

[d6c663f33626485e9ee19ad70b70fdd9.png]: /images/20220828/22adbffd71094b3e8b709980e01b3740.png