动态规划

在学动态规划之前，要先学回溯算法，作为动态规划的基础。

回溯算法

本质上，就是一个有序的遍历：

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

对于例题一，访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。

void preOrder(TreeNode* root){
    if(root == nullptr){
        return;
    }
    //尝试
    path.push_back(root);
    if(root->val == 7){
        //记录解
        res.push_back(path);
    }
    preOrder(root->left);
    preOrder(root->right);
    //回退
    path.pop_back();
}

框架代码

/*回溯算法框架*/
void backtrack(State* state, vector<choice*>& choices, vector<state*>& res) {
    //判断是否为解
    if (isSolution(state)) {
        //记录解
        recordSolution(state, res);
        //不再继续搜索
        return;
    }
    //遍历所有选择
    for (Choice choice : choices) {
        //剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            //尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            //回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

‍