Guderian出品
假币问题： 有$ n $枚硬币， 其中有一枚是假币， 己知假币的重量较轻。 现只有一个天平， 要求用尽量少的比较次数找出这枚假币。
算法设计策略：分治法
将 n 枚硬币分成相等的两部分:
(1)当$ n $为偶数时， 将前后两部分， 即$ 1…n/2 $和$ n/2+1…n$， 放在天平的两端， 较轻的一端里有假币， 继续在较轻的这部分硬币中用同样的方法找出假币:
(2)当$ n $为奇数时， 将前后两部分， 即$1..(n -1)/2$和$(n+1)/2+1…n$， 放在天平的两端， 较轻的一端里有假币， 继续在较轻的这部分硬币中用同样的方法找出假币； 若两端重量相等， 则中间的硬币， 即第$ (n+1)/2 $枚硬币是假币。
（1）常量和变量说明
coins[]：硬币数组
first，last：当前考虑的硬币数组中的第一个和最后一个下标
Guderian出品
一个无向连通图$ G $点上的哈密尔顿（Hamiltion） 回路是指从图$ G $上的某个顶点出发， 经过图上所有其他顶点一次且仅一次， 最后回到该顶点的路径。
算法设计策略：回溯法+深度优先搜索+记忆化搜索
假设图$ G $存在一个从顶点$ V_0 $出发的哈密尔顿回路$ V_1-V_2-V_3-…-V_{n-1}-V_0$。算法从顶点$ V_0 $出发， 访问该顶点的一个未被访问的邻接顶点$ V_1$， 接着从顶点$ V_1 $出发， 访问$ V_1 $一个未被访问的邻接顶点$ V_2$，以此类推。对顶点$ V_i$， 重复进行以下操作： 访问$ V_i $的一个未被访问的邻接接点$ V_{i+1}$； 若$ V_i $的所有邻接顶点均已被访问， 则返回到顶点$ V_{i-1}$， 考虑$V_{i-1} $的下一个未被访问的邻接顶点， 仍记为$ V_i$； 知道找到一条哈密尔顿回路或者找不到哈密尔顿回路， 算法结束。
（1）常量和变量说明
n：图$G$中的顶点数
c[][]：图$G$的邻接矩阵
k：统计变量，当前已经访问的顶点数为k+1
x[k]：第k个访问的顶点编号，从0开始
visited[x[k]]：第k个顶点的访问标志，0表示未访问，1表示已访问
故宫 by Gigi
Guderian出品
某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表$ P$，其中中 $P_i（i＝1，2，…，m）$表示长度为$i$英寸的钢条的价格。现要求解使销售收益最大的切割方案 。
算法设计策略：动态规划
假设长钢条的长度为$ n $英寸，最佳切割方案的最左边切割段长度为$ i $英寸，则继续求解剩余长度为$ n－i $英寸钢条的最佳切割方案。考虑所有可能的$ i$，得到的最大收益$ r_n$对应的切割方案即为最佳切割方案。$r_n$的递归定义如下：
对此递归式，给出自顶向下和自底向上两种实现方式。
Aurora
Guderian出品
给定一个字符$B=b_1 b_2\dots b_n$，其中$b_i \in \{A,C,G,U\}$。$B$上的二级结构是一组字符对集合$S=\{(b_i,b_j)\}$，其中$i,j\in \{1,2,\dots ,n\}$，并满足以下四个条件：
（1）$S$中的每对字符是$(A,U),(U,A),(C,G),(G,C)$四种组合之一；
（2）$S$中的每对字符之间至少有四个字符将其隔开，即$i<j-4$；
（3）$S$中的每一个字符（记为$b_k$）的配对存在两种情况：$b_k$不参与任何配对；$b_k$和$b_t$配对，其中$t<k-4$；
（4）（不交叉原则）若$(b_i,b_j)$和$(b_k,b_l)$是$S$种的两个字符对，且$i<k$，则$i<k<j<l$不成立。
$B$的具有最大可能字符对数的二级结构$S$被称为最优配对方案，求解最优配对方案中的字符对数的方法如下：
假设用$C(i,j)$表示字符序列$b_i b_{i+1} \dots b_j$的最优配对方案（即二级结构$S$）中的字符对数，则$C(i,j)$可以递归定义为：
题目的第3个条件容易引起歧义，一种不影响作答的理解是：$B$上的字符要么不配对，要配对就要相隔至少4个字符。当然可以直接忽略这个条件，因为题目已经给出了足够多的信息了。
显然题目说明最后的方程是动态规划算法中的状态转移方程，这提示我们这道题目的算法思想是动态规划。因此我们采取的做法是：从较小的区间开始，转移到较大的区间，直到覆盖$B$中所有字符。
Guderian出品
n皇后问题描述为：在一个$n \times n$的棋盘上摆放$n$个皇后，要求任意两个皇后不能冲突，即任意两个皇后不再同一行、同一列、同一斜线上。
算法设计策略：回溯法
将第$i$个皇后摆放在第$i$行，$i$从$1$开始，每个皇后都从第$1$列开始尝试。尝试时判断再该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。
如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后，以此类推，直到找到所有合理的摆放方案。