回溯算法和LRU

回溯算法实现（DFS） 回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法 递归遍历二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def back_track(nums, track, res): # 结束条件 if len(nums)== len(track): # res.extend(track) # 正常 res.append(track)# 不正常 return None # 遍历选择列表 for num in nums: if num in track: continue track.append(num) back_track(nums, track.copy(), res) track.pop() return None if __name__ == '__main__': nums =[1, 2, 3] track =[] res =[] back_track(nums, track, res) print(res) 某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。 LRU（Least recently used）算法实现 LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 ...