动态规划

0. 最大子串和
〖题目描述〗
在一个一维数组里找出连续的几个数，使数的总和最大。

1. 最短路（Shortest path）
〖题目描述〗
从A地到E地可以经过不同的路径，不同的路有不同的发费，问如何走可以得到耗费最少的
路径？

2. 最小中间和数
〖题目描述〗
给定一个正整数序列a1,a2,a3,……,an不改变序列中每个在序列中的位置，把它们相加，
并括号记每次加法所得的和，称为中间和。问如何加括号可以使所有的中间和相加为最少
。

3. 最长公共子序列问题：
〖题目描述〗
给定两个序列x=……,xn>和y=……,ym>,要求找出x和y 的一个最长公共
子序列。

4、防卫导弹：
〖题目描述〗
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞
行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发
射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导
弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导
弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的
高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的
进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
1、它是该次测试中第一个被防卫导弹截击的导弹；
2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹
。