习题：
1、汽车加油问题：
设有路程长度为L公里的公路上，分布着m个加油站，它们的位置分别为p[i]（i=1，2，……，m），而汽车油箱加满油后（油箱最多可以加油k升），可以行驶n公里。设计一个方案，使汽车经过此公路的加油次数尽量少（汽车出发时是加满油的）。
2、最短路径：
设有一个网络，要求从某个顶点出发到其他顶点的最短路径
3、跳马问题：
在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
4、二叉树的遍历
5、背包问题
6、用分治法实现两个大整数相乘
7、设x1，x2，…，xn是直线上的n个点，若要用单位长度的闭区间去覆盖这n个点，至少需要多少个这样的单位闭区间？
8、用关系“＜”和“＝”将3个数A、B和C依次排列时，有13种不同的序关系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要将n个数依序进行排列，试设计一个动态规划算法，计算出有多少钟不同的序关系。
9、有一种单人玩的游戏：设有n(2<=n<=200)堆薄片，各堆顺序用0至 n-1编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到该堆的相邻堆上。如指定
I堆k张 k 移到I-1(I>0)堆，和将k 张薄片移至I+1(I<n-1)堆。所以当有两个堆与 I 堆相邻 时，I堆原先至少有2k 张薄片；只有一个堆与 I 堆相邻 时， I 堆原先至少有k张薄片。
游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使 各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：
设
ci:I堆的薄片数(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片数；
ai:I堆的相邻堆可以从I堆得到的薄片数。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
这里并不希望准确地求出A0 至an-1，而是作以下处理：若令 a0 为0，能按上述算式计算出 A1至 an-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去的薄片数大于等于0。
实际操作采用以下贪心策略：
（1）每次从第一堆出发顺序搜索每一堆，若发现可从 I堆移走薄片，就完成一次移动。即， I堆的相邻堆从 I堆取走 ai片薄片。可从I 堆移薄片到相邻堆取于 I堆薄片数：若I 堆是处于两端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中间堆，则要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也最多。在用策略（1）搜索移动时，当发生没有满足条件（1）的可移走薄片的堆时，采用本策略，让在ai>0的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。
1、汽车加油问题：
设有路程长度为L公里的公路上，分布着m个加油站，它们的位置分别为p[i]（i=1，2，……，m），而汽车油箱加满油后（油箱最多可以加油k升），可以行驶n公里。设计一个方案，使汽车经过此公路的加油次数尽量少（汽车出发时是加满油的）。
2、最短路径：
设有一个网络，要求从某个顶点出发到其他顶点的最短路径
3、跳马问题：
在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
4、二叉树的遍历
5、背包问题
6、用分治法实现两个大整数相乘
7、设x1，x2，…，xn是直线上的n个点，若要用单位长度的闭区间去覆盖这n个点，至少需要多少个这样的单位闭区间？
8、用关系“＜”和“＝”将3个数A、B和C依次排列时，有13种不同的序关系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要将n个数依序进行排列，试设计一个动态规划算法，计算出有多少钟不同的序关系。
9、有一种单人玩的游戏：设有n(2<=n<=200)堆薄片，各堆顺序用0至 n-1编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到该堆的相邻堆上。如指定
I堆k张 k 移到I-1(I>0)堆，和将k 张薄片移至I+1(I<n-1)堆。所以当有两个堆与 I 堆相邻 时，I堆原先至少有2k 张薄片；只有一个堆与 I 堆相邻 时， I 堆原先至少有k张薄片。
游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使 各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：
设
ci:I堆的薄片数(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片数；
ai:I堆的相邻堆可以从I堆得到的薄片数。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
这里并不希望准确地求出A0 至an-1，而是作以下处理：若令 a0 为0，能按上述算式计算出 A1至 an-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去的薄片数大于等于0。
实际操作采用以下贪心策略：
（1）每次从第一堆出发顺序搜索每一堆，若发现可从 I堆移走薄片，就完成一次移动。即， I堆的相邻堆从 I堆取走 ai片薄片。可从I 堆移薄片到相邻堆取于 I堆薄片数：若I 堆是处于两端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中间堆，则要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也最多。在用策略（1）搜索移动时，当发生没有满足条件（1）的可移走薄片的堆时，采用本策略，让在ai>0的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。