算法的本质就是穷举“遍历”和“分解问题”是穷举的两大思维模式。回溯一个传话兵自始至终只有“一个你在走”。你走进了 A 房间在墙上写了个字做选择发现是死胡同你必须把字擦掉撤销退出来才能再去 B 房间。因为如果你不擦B 房间的人就会看到 A 房间的字这就把状态污染了。DP分身术你站在门口直接克隆了两个自己通过函数调用传入不同的参数比如 start_idx length。克隆人 A 去了 A 房间克隆人 B 去了 B 房间。克隆人 A 就算在里面把房间砸了也丝毫不影响克隆人 B。他们执行完任务只要把结果“喊”给你听就行了。说白了回溯自始至终就一个传话兵所以要撤销再去不同的房间。DP每到一个路口会分出不同的传话兵去不同的房间然后汇报完就不用管了。如果都不用备忘录的话回溯和DP做的事情差不多。如果都用备忘录的话回溯和DP做的事情也差不多。为什么说“没有备忘录时做的事情差不多”在没有备忘录的情况下无论是回溯还是自顶向下的 DP它们在计算机底层内存栈中遍历的节点总数、访问的路径顺序、以及总的时间复杂度是完全一模一样的。它们都在做一件事情盲目地穷举这棵巨大的决策树。唯一的微小区别只是回溯通过一个全局变量在记录“我走过哪”而 DP 通过函数的返回值在告诉上一层“我看到了什么”。但论干的“苦力活”计算量它们不相上下都会超时。为什么说“有备忘录时做的事情也差不多”一旦加上了备忘录它们就同时拥有了“天眼”回溯的那个传话兵走到一个路口看一眼公告牌备忘录“哦以前的分身来过这说前面是死胡同。” 传话兵立刻掉头省去了无数步路。DP 的分身走到同一个路口看一眼公告牌“哦别的分身已经算过了。” 这个分身当场消失返回结果不再继续克隆新的分身。所以加了备忘录后它们都从“指数级”变成了“多项式级的高效剪枝”做的事情依然是高度等价的。个人总结分出不同的传令兵就对应分解问题自始至终只有一个传令兵那实际上就是靠他去遍历。