《动态规划方法例题讲述》由会员分享，可在线阅读，更多相关《动态规划方法例题讲述（50页珍藏版）》请在金锄头文库上搜索。
1、动态规划方法例题 最长上升子序列问题 一个序列有N个数：A1,A2,AN，求 出最长上升子序列的长度（LIS：longest increasing subsequence)。 例如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的 一些上升子序列，如(1, 7), (3, 5, 9) , (3, 4, 8)等等。这些子序列中最长的长度是4，比 如子序列(1, 3, 5, 9) ，(1, 3, 5, 8)和(1, 3, 4, 8). 分析 假如我们考虑求A1,A2,Ai的最长上升 子序列的长度，其中ilen) len = di; 序列变化 求最长非降子序列(longest non-de
2、creasing subsequence)，与此问题近似。只需要将上述条 件Ajlen) len = di; 例2 乘积最大 问题描述 设有一个长度N的数字串，要求选手使用K个乘号将它分 成K+1个部分，找出一种分法，使得这K+1个部分的乘积 能够为最大。 例子：有一个数字串: 312，当N=3，K=1时会有以下两种 分法： 1）3*12=36 2）31*2=62 这时，符合题目要求的结果是： 31*2=62 现在，请你设计一个程序，求得正确的答案。 （蓝桥网站题目编号：ALGO-17 VIP试题2013-11-07 ） 输入输出样例 输入： 输入中有若干组测试数据，每组测试数据有两行：第 一
3、行共有2个自然数T，K （6=vi)*/ 例5 装箱问题 有一个箱子容量为V（正整数，0V20000），同时 有n个物品（0n30），每个物品有一个体积（正整 数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余 空间为最小。 输入格式 第一行为一个整数，表示箱子容量； 第二行为一个整数，表示有n个物品； 接下来n行，每行一个整数表示这n个物品的各自体积。 输出格式 一个整数，表示箱子剩余空间。 蓝桥网编号：ALGO-21 VIP试题 2013-11-07 输入输出样例 样例输入 24 6 8 3 12 7 9 7 样例输出 0 分析 这是一个变形的背包问题，最优目标是：使 箱子的剩余空间
4、为最小。可转换成物品占 据的容量最大。 用Fi,j表示容量为j的箱子装入前i个物品后， 物品占据的容量。则状态转移方程为： Fi,j= maxFi-1,j-ai+ai，Fi-1,j 其中ai表示第i个物品的体积。 主要代码段 dp0=0;/注意这是关键 for(i=0;i=a;j-) dpj=max(dpj,dpj-a+a); 收集苹果：二维的DP问题 平面上有NM个格子，每个格子中放着一 定数量的苹果。你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到 一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果。 我们必须注意到的一点是，到达一个格子 的方式最多只有两
5、种：从左边来的(除了第 一列)和从上边来的(除了第一行)。 分析 因此为了求出到达当 前格子后最多能收集 到多少个苹果，我们 就要先去考察那些能 到达当前这个格子(i,j) 之前的格子，到达它 们最多能收集到多少 个苹果。 (i-1,j) (i,j-1)(i,j) Ai,j 状态和状态转移方程 状态Sij表示我们走到(i, j)这个格子时，最 多能收集到多少个苹果。 那么，状态转移方程如下： Sij=Aij + max(Si-1j, if i0 ; Sij-1, if j0) 其中i代表行，j代表列，下标均从0开始； Aij代表格子(i, j)处的苹果数量。 例6 传纸条 小渊和小轩是好朋友也
6、是同班同学，他们在一起总有谈不完的话题。 一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊 和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸 运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对 方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角， 坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩 传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回 复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如 果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就
7、 不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（ 注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一 个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能 找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这 两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到 这样的两条路径。 蓝桥网题目编号：ALGO-36VIP试题2013-11-08 输入输出格式 输入格式 输入第一行有2个用空格隔开的整数m和n，表 示班里有m行n列（1=m,n=50）。 接下来的m行是一个m*n的矩阵，矩阵中第i 行j列的整数表示坐在
8、第i行j列的学生的好心程度 。每行的n个整数之间用空格隔开。 输出格式 输出一行，包含一个整数，表示来回两条路上 参与传递纸条的学生的好心程度之和的最大值。 样例输入输出 样例输入 3 3 0 3 9 2 8 5 5 7 0 样例输出 34 数据规模和约定 30%的数据满足：1=m,n=10 100%的数据满足：1=m,n=50 传纸条(甩干后) 小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩 阵的右下角，坐标(m,n)。从小渊传到小轩的纸条 只可以向下或者向右传递，从小轩传给小渊的纸 条只可以向上或者向左传递。 班里每个同学都可以帮他们传递，但只会帮他们 一次。 每个同学愿意帮忙的好感度有
9、高有低，可以用一 个0-100的自然数来表示，数越大表示越好心。 小渊和小轩希望尽可能找好心程度高的同学来帮 忙传纸条，即找到来回两条传递路径，使得这两 条路径上同学的好心程度之和最大。现在，请你 帮助小渊和小轩找到这样的两条路径。 1=m,n=50 贪心 很容易想到一个算法： 求出1个纸条从（1，1）到（M,N）的路线最大值. 删除路径上的点值 再求出1个纸条从（M,N） 到（1，1）的路线最大值. 统计两次和 上述算法很容易找出反例，如下图。 第1次找最优值传递后，导致第2次无法传递。 分析 贪心算法错误，因此我们需要同时考虑两个纸条的传递。 由于小渊和小轩的路径可逆，因此，尽管出发点不同
10、，但 都可以看成同时从(1,1)出发到达(M,N)点。 设f(i1,j1,i2,j2)表示纸条1到达(i1,j1)位置，纸条2到达(i2,j2)位 置的最优值。则有， 其中 (i1,j1)!= (i2,j2) 1=i1, i2=M, 1=j1 , j2=N 时间复杂度O(N2M2) 地宫取宝 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子 放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角，出口在右下角。 小明被带到地宫的入口，国王要求他只能向右或向下行 走。 走过某个格子时，如果那个格子中的宝贝价值比小明手 中任意宝贝价值都大，小明就可以拿起它（当然，也可以 不拿）。 当
11、小明走到出口时，如果他手中的宝贝恰好是k件，则 这些宝贝就可以送给小明。 请你帮小明算一算，在给定的局面下，他有多少种不同 的行动方案能获得这k件宝贝。 蓝桥网编号：PREV-28 地宫取宝 普通试题2014-03-25 输入输出格式 输入格式 输入一行3个整数，用空格分开：n m k (1=n,m=50, 1=k=12) 接下来有 n 行数据，每行有 m 个整数 Ci (0=Ci=12)代表这个格子上的宝物的价值 输出格式 要求输出一个整数，表示正好取k个宝贝 的行动方案数。该数字可能很大，输出它 对 1000000007 取模的结果。 输入输出样例 样例输入 2 2 2 1 2 2 1 样例输出 2 样例输入 2 3 2 1 2 3 2 1 5 样例输出 14
