一类折返问题
直线折返问题
考虑这样一个问题，有$n$个位置$1,\ldots,n$，你初始站在位置$s$。每个位置可能有金币和没有金币，保证$s$处没有金币。当你第一次路过（到达）某个有金币的位置时候，你不能直接将其捡起，你只能在之后再次到达（离开后再次进入）这个位置后才能将其捡起。从位置$i$到$j$花费的时间为$|i-j|$。问要捡起所有金币最少需要走的路径长度为多少（不需要返回$s$）。
最优解的情况下我们必定是捡起所有左边的金币后再去捡起所有右边金币，或者捡起所有右边的金币后再去捡起所有左边金币。
我们考虑捡起所有左边的金币后再去捡起所有右边金币的情况（另外一种情况类似），由于去了左边后要回到原点$s$，记$x$为左边下标最小的一个有金币的位置，则左边的费用为$2(s-x)$。而右边的计算和左边独立。对于右边我们不需要回到$s$，所以算起来比较麻烦。
我们可以用动态规划来计算，定义$dp_i(0)$表示移动到$i$处且$(s,i)$之间所有金币已经收集完成的最少费用；$dp_i(1)$表示移动到$i$处，且在$(s,i)$处有至少一个金币没有拾起，且最终需要折返收集，并回到当前位置的最少费用；$dp_i(2)$表示移动到$i$处，且在$(s,i)$处有至少一个金币没有拾起，且最终需要折返收集，但是不需要回到当前位置的最少费用。可以发现$dp_i$到$dp_{i+1}$的转移可以$O(1)$计算完成。
因此总的时间复杂度为$O(n)$。
提供一道题目。
树上折返问题
考虑这样一个问题，有一个$n$个结点的树，你需要选择一条最短的路径（包含最少的边数），要求每个顶点至少遍历一次。
如果是需要回到起点，则答案一定是$2(n-1)$，因为每条边都需要至少遍历两次。
但是这里不需要返回起点，我们可以用一种取巧的方式，因为答案为$2(n-1)-x$，其中$x$为仅被遍历一次的边数，可以发现仅被遍历一次的边正好也能组成一条路径。因此$x$最大的情况下，被遍历一次的边恰好组成了树的直径。而计算树上直径是非常简单的。