重叠子问题

可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

排队和栈(Queue和stack)

排队和栈是动态改变的数据结构．任何时候它们都包含一组有序的项．对排队的情形来说，如果添加一项，就把它放在组的末端，而且只能从定义该排队组的前面取出或移摔项．列在排队中的第一项是唯一可取出的项，而且必须先移掉它．对栈的情形来说，添加的项同样是放在组的末端，不同的是要从组的末端取出和移掉项．此时最后添加的项是唯一可取出的项，并最先被移掉．项可以是可变长度的，并在项中指明其长度．