result = []

def backtrack(路径, 选择列表):

    if 满足结束条件:

        result.add(路径)

        return

    for 选择 in 选择列表:

        做选择

        backtrack(路径, 选择列表)

        撤销选择

// 计算从起点 start 到终点 target 的最近距离

int BFS(Node start, Node target) {

    Queue<Node> q; // 核心数据结构

    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列

    visited.add(start);

    int step = 0; // 记录扩散的步数

    while (q not empty) {

        int sz = q.size();

        /* 将当前队列中的所有节点向四周扩散 */

        for (int i = 0; i < sz; i++) {

            Node cur = q.poll();

            /* 划重点：这里判断是否到达终点 */

            if (cur is target)

                return step;

            /* 将 cur 的相邻节点加入队列 */

            for (Node x : cur.adj())

                if (x not in visited) {

                    q.offer(x);

                    visited.add(x);

                }

        }

        /* 划重点：更新步数在这里 */

        step++;

    }

}

int left_bound(int[] nums, int target) {

    int left = 0, right = nums.length - 1;

    // 搜索区间为 [left, right]

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {

            // 搜索区间变为 [mid+1, right]

            left = mid + 1;

        } else if (nums[mid] > target) {

            // 搜索区间变为 [left, mid-1]

            right = mid - 1;

        } else if (nums[mid] == target) {

            // 收缩右侧边界

            right = mid - 1;

        }

    }

    // 检查出界情况

    if (left >= nums.length || nums[left] != target)

        return -1;

    return left;

}

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

int res = Math.max(

            // 不抢，去下家

            dp(nums, start + 1),

            // 抢，去下下家

            nums[start] + dp(nums, start + 2)

        );

Map<TreeNode, Integer> memo = new HashMap<>();

public int rob(TreeNode root) {

    if (root == null) return 0;

    // 利用备忘录消除重叠子问题

    if (memo.containsKey(root))

        return memo.get(root);

    // 抢，然后去下下家

    int do_it = root.val

        + (root.left == null ?

            0 : rob(root.left.left) + rob(root.left.right))

        + (root.right == null ?

            0 : rob(root.right.left) + rob(root.right.right));

    // 不抢，然后去下家

    int not_do = rob(root.left) + rob(root.right);

    int res = Math.max(do_it, not_do);

    memo.put(root, res);

    return res;

}

dp[i][w] = max( 把物品i装进背包, 不把物品i装进背包 )　

dp[i][w] = max(dp[i-1][w],  dp[i-1][w - wt[i-1]] + val[i-1] )

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {

    // vector 全填入 0，base case 已初始化

    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= N; i++) {

        for (int w = 1; w <= W; w++) {

            if (w - wt[i-1] < 0) {

                // 当前背包容量装不下，只能选择不装入背包

                dp[i][w] = dp[i - 1][w];

            } else {

                // 装入或者不装入背包，择优

                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1],

                               dp[i - 1][w]);

            }

        }

    }

    return dp[N][W];

}