我们毕业啦其实是答辩的标题地方1.实验题目编程实现图示多段图的最短路径问题的动态规划算法2．实验目的（1）理解动态规划算法的概念；（2）掌握动态规划算法的基本要素；（3）掌握设计动态规划算法的步骤；（4）通过应用范例学习动态规划算法的设计技巧与策略。1.实验题目给定由n个整数组成的序列(a1,a2,…,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。1.实验题目给定由n个整数组成的序列(a1,a2,…,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。6.3实验项目——编辑距离大家应该也有点累了，稍作休息【输入】：输入包含若干大象的数据，每行一头大象，直到输入结束。每头大象的数据包括两个整数：第一个是以千克为单位的体重，第二个是以整百为单位的IQ指数。两个整数均在1到10000之间。输入最多包含1000头大象。两头大象可能有相同的体重，或者相同的IQ，甚至体重和IQ都相同。【输出】：输出第一行应当包括一个整数n，为找到的大象序列的长度。接下来的n行，每行包含一个正整数，表示大象。用W[i]和S[i]表示输入数据中第i行的两个数，则若找到的这一序列为a[1]，a[2]，...，a[n]，则必须有：W[a[1]]<W[a[2]]<...<W[a[n]]和S[a[1]]>S[a[2]]>...>S[a[n]]i首先将所有大象按体重W[i]升序排列，这样该问题就转化为了最长上升递减子序列LIS（LongestIncreasingSubsequence）问题。定义状态d(i)，代表前i个大象中以大象i作为序列结尾的最长上升子序列的长度。状态转移方程：d(i)=max{d(k)+1|1<=k<i,W[k]<W[i],S[k]>S[i]}练习2：1092回文字符串练习3：华为机试-购物单（0-1背包+限制条件）如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助王强设计一个满足要求的购物单。输入描述:输入的第1行，为两个正整数，用一个空格隔开：Nm（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）输出描述:输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。