实验报告课程算法设计与分析实验实验名称动态规划算法设计与应用第 1 页一、实验目的1. 加深对动态规划算法的基本原理的理解，掌握用动态规划方法求解最优化问题的方法步骤及应用；2. 用动态规划设计整数序列的最长递增子序列问题的算法，分析其复杂性， 并实现；3. 用动态规划设计求凸多边形的三角剖分问题的算法，分析其复杂性，并实现。4. 选做题：用动态规划设计求解0/1 背包问题的算法，分析其复杂性，并实现。二、实验内容(一) 最长递增子序列问题1. 问题描述求一个由 n 个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。最长递增子序列是其递增子序列中长度最长的。2. 具体要求（若在 ACM平台上提交程序，必须按此要求）――平台上1700题输入：输入的第一行是一个正整数n，表示测试例个数。接下来几行是n 个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数k (k<=500) ，表示整数序列的长度， 第二行给出整数序列， 整数之间用一个空格隔开。（设给出的每个整数序列的最长递增子序列都是唯一的。）输出：对于每个测试例输出两行， 第一行为最长递增子序列的长度，第二行为最长递增子序列， 整数之间用一个空格隔开。 两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。3. 测试数据输入： 3 5 3 1 4 2 3 6 1 3 9 5 2 6 20 1 2 7 13 3 5 10 24 12 4 9 16 53 6 83 8 23 11 31 47 输出： 3 1 2 3 4 1 3 5 6 10 1 2 3 5 10 12 16 23 31 47 4. 设计与实现的提示(1) 寻找最优子结构、写出递归方程是问题的关键。(2) 以 Ai 为末元素的最长递增子序列( 记为 S(i)) ，等于以使 S(j), (j=1～i), 最大的那个Aj 为末元素的递增子序列最末再加上Ai ；如果这样的元素不存在，那么 Ai 自身构成一个长度为1 的以 Ai 为末元素的递增子序列。(3) 最优解的信息在此是以Ai 为末元素的最长递增子序列的前驱元素，应当记录下来。5. 扩展内容本题可以采用多种方法求解，可以尝试用不同思路求解。( 二) 凸多边形的三角剖分1. 问题描述设 P 是一个有 n 个顶点的凸多边形， P 中的弦是 P 中连接两个非相邻顶点的线段。用 P中的(n-3) 条弦将 P剖分成 (n-2) 个三角形 （如下图所示）。使得(n-3)条 弦 的 长 度 之 和 最 小 的 三...
