算法设计与分析——第4章 动态规划
一、动态规划的基本思想
二、设计动态规划法的步骤
三、动态规划问题的特征
矩阵连乘积问题
分析最优解的结构
分析最优解的结构
动态规划算法的基本要素
最长公共子序列
最大子段和
¢给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。
l当所有整数均为负值时定义其最大子段和为0。
¢所求的最优值为：
l
l例如，当(a1,a2, ……a7,a8)=(1,-3, 7,8,-4,12, -10,6)时，
最大子段和为：
最大子段和为：
0－1背包问题
最长单调递增子序列
最多拦截导弹数
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它能拦截任意高度的导弹，但是每拦截一发导弹，其拦截能力就下降到只能拦截上一次拦截的导弹高度。
某天，雷达捕捉到敌国的导弹来袭，导弹依次飞来，该拦截系统最多能拦截多少导弹呢？
¢Input:
输入若干组数据。每组数据包括：导弹总个数（正整数<1000），导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，用空格分隔）。若导弹个数为0，则处理结束。
¢Output:
输出这套系统最多能拦截多少导弹。
数字三角形问题