文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 动态规划 最长子串与最大子矩阵问题
侵权投诉

动态规划 最长子串与最大子矩阵问题

动态规划与分治的基本思想一致,都是将整个问题分解为子问题,然后解子问题进而求得原问题。然而,两者又有本质的不同:

动态规划 最长子串与最大子矩阵问题

动态规划与分治的基本思想一致,都是将整个问题分解为子问题,然后解子问题进而求得原问题。然而,两者又有本质的不同:

动态规划 最长子串与最大子矩阵问题

分治中的子问题相互独立,解得所有子问题后,组合起来就是原问题;

动态规划中的子问题不是相互独立的,后一个子问题的解往往要用到前一个子问题的解。这从下面要分析的最长子串问题中可以看得很清楚。动态规划从一个最简单的子问题着手,然后每一步的结果都被保存,供下一个子问题使用。

动态规划只适用于具有最优子结构的问题,即,局部最优解能决定全局最优解。这样,我们才能将其划分为子问题来解决。

动态规划总体上来说是一个多阶段决策过程,而且这个决策问题应该具有马尔科夫性,即(下一个决策只与前一个决策有关)。下面提到的最优化原理,就是指“最优过程的部分也一定是最优的”

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题

具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次

产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

3. 最终,我们可以得到下面这个递归式:f(k,x) = h( d, f(k-1,x-1) ) 其中k表示迭代

次数,其中h是求当前最优解的一个函数,f(k,x)表示第k次的最优值,d表示问题变化的量。

先把代码贴上来吧,明天再解释。

最长子串:

其实,动态规划的思路就是每一步都求子问题的最优解,然后迭代到最后就是整个问题的最优解。求最长子串的思路也一样,我们从串的第一个值开始,每次都选取最大的子串。

假设有子串a1,a2.....an ,我们已经求得子串a1......aj(1<= j <= n)的最长子串是b , 那么我们现在记录b的值,然后计算a1 ....aj,a(j+1)【其实这个子串可以看做是 b, a(j+1)】的最长子串,那么它的最长子串就是 b+a(j+1)和a(j+1) 中的较大者。

#include <iostream>

#include <vector>

第1页

你可能喜欢

热门文档

相关文档

  • 动态规划100例

    24 线型动态规划 2 最长公共子串,LCS 问题... 24...56 最大子矩阵问题 4 最大子立方体问题 ... 56 最大子矩阵问题 5 居住空间 ......

  • 动态规划求解最长公共子串问题

    动态规划求解最长公共子串问题_经管营销_专业资料。高考历史、文综历史专题复习【全部完成】算法思想 求字符串str1,str2的最长公共子串的长度。 定义二元函数函数...

  • 动态规划总结

    线型动态规划3 ---最长公共子串,LCS问题 f[i,j]=0 (i=0)&(j=0); ...[c,i,j]); 54 最大子矩阵问题 ---居住空间 f[i,j,k]:=min(min(min...

  • 动态规划

    线型动态规划3 ---最长公共子串,LCS问题 f[i,j]={0(i=0)&(j=0); ...[i-1,j]); 71 最大子矩阵问题 ---最大字段和问题 f:=max(f[i-1]+...

  • 动态规划求解最长公共子串问题

    动态规划求解最长公共子串问题应用技术研究 浅析供应链冲突及其管理范庆玉 [文章摘要]供应链企业间的冲突...

  • 动态规划状态转移方程

    线型动态规划 3 ---最长公共子串, ---最长公共子串,LCS 问题 最长公共子...[c,i,j]) 54 最大子矩阵问题 ---居住空间 ---居住空间 f[i,j,k]:=...

  • 最大子矩阵问题总结

    最大子矩阵问题总结_计算机软件及应用_IT/计算机_专业资料。动态规划中的几个最大子矩阵问题题目来源 hduLargest Rectangle in a Histogram Time Limit : 2000/...

  • 最大字段问题-含最大子矩阵和m子段和

    最大字段问题-含最大子矩阵和m子段和_天文/地理_自然科学_专业资料。最大...else b = a[i]; if(b>sum){ sum = b; } } 动态规划法的计算时间...

  • 100个动态规划方程

    线型动态规划 3---最长公共子串,LCS 问题 f[i,j]={0(i=0)&(j=0);...[c,i,j]) 54 最大子矩阵问题---居住空间 f[i,j,k]:=min(min(min(f...

  • 动态规划模拟试卷及答案

    50 分) 1、用动态规划算法实现最长公共子序列问题...规划算法实现下列问题:设 A 和 B 是两个字符串。...最大子矩阵的问题 二、简答题 1、 (1)找出最优...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email