在以往的算法课程中，比如《算法导论》和国内的《数据结构和算法》，都是先讲授数据结构，然后再讲算法。而Algorithmic Toolbox这门系列课程另辟蹊径，不仅是先讲算法，再讲数据结构（第一门课程中讲授算法、第二门课程中讲授数据结构），而且是先讲贪心算法，再讲动态规划（在算法导论中是先讲动态规划，再讲贪心算法的）。
在这周的贪心算法课程中，老师讲了三个例子。第一个是求长途旅行需要加油的最少次数。条件如下所示：
1:在满载不加油的情况下，最多行驶400KM。
2:起点为A，终点为B，距离为950KM。
解算法题的两大步骤：第一步先把算法问题进行数学建模，第二步用程序表示数学建模的思想。以此题为例，第一步数学建模，结果如下：
Input: A car which can travel at most L kilometers with full tank, a source point A, a destination point B and n gas stations at distances x1 ≤ x2 ≤ x3 ≤ · · · ≤ xn in kilometers from A along the path from A to B.
Output: The minimum number of refills to get from A to B, besides refill at A.（目标函数）
一共有几种决策方式，分别是在最近的加油站加油、在油量不耗尽的前提下在最远的加油站加油、一直开不加油等等（例如在决策1和2之间的加油站加油）。
决策2的具体步骤如下所示：
- Start at A
- Refill at the farthest reachable gas station G
- Make G the new A
- Get from new A to B with minimum number of refills
其中1、2、3步是个循环直到结束。
其中在贪心算法中有个核心概念是safe move，即if there exists some optimal solution in which first move is this greedy choice, then this greedy choice is called a safe move.
在这里，证明的方式像是寻找和first move不同的情况下，最后还是等效或者不如first move的情况。在这里，由于G是不耗尽油的最远加油站，所以除了first move选择G以外，我们只能选择G1。如下图所示：
在这里，其实细分的话，可以分为3种情况。G2>G, G2=G, G2<G。
当G2=G时，很显然，多加了一次油，也就是不如的情况。
当G2<G时，这里也没必要在G1地方加第一次油，也是不如的情况。
伪代码如下所示，其中外层循环指代的是每次加油，内层循环指代的是每次加油的具体地点：
A = x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn ≤ xn+1 = B
MinRefills(x, n, L)
numRefills ← 0, currentRefill ← 0
while currentRefill ≤ n:
lastRefill ← currentRefill
while (currentRefill ≤ n and x[currentRefill + 1] − x[lastRefill ] ≤ L):
currentRefill ← currentRefill + 1
if currentRefill == lastRefill:
return IMPOSSIBLE
if currentRefill ≤ n:
numRefills ← numRefills + 1
return numRefills
