On this page

动态规划，回溯问题，DFS的联系与区别

核心相同点还是二叉树的递归遍历理解

动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。
回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
DFS 算法属于遍历的思路，它的关注点在单个「节点」。

因为关注点不一样，所以就是写代码的位置不太一样

动态规划框架

js

function traverse(){
    //根据缓存决定还不要进行下面的递归
    if(cache[n])return cache[n];
   //递归出口
    if(xxx)return 出口值


    for(let 选择 of 所有选择){
        let result=traverse()
        //缓存result
        //根据状态转移方程和缓存，维护最优值
    }
    return 最优值
}

回溯框架

js

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

DFS框架

js

function traverse(){
    
    //进入节点
    for(let 选择 of 所有选择){
       traverse()
    }
    //出节点
}