题目描述 Description
给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。
概念
适用于动态规划求解的问题，经过分解得到的问题往往不是相互独立的。若用分治算法来解这类问题，子问题常常被计算多次。动态规划的基本思想是，将计算过的子问题存储到一个表中，来避免重复计算。
动态规划的基本要素
最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构的性质。
重叠子问题：当采用递归的方式计算问题时，相同的子问题被重复计算多次。
设计动态规划算法的步骤
- 找出最优解的性质，并刻画其结构特征
- 递归定义最优值
- 自底向上的方式计算出最优值
- 根据计算最优值时得到的信息，构造最优解。
