问题: 已知字符串 B 是字符串 A 的一个子串,问字符串 B 在字符串 A 的第一次出现位置.  暴力方法:从 A 字符串 的每个位置开始对字符串 B 进行匹配. 这种方法根据数据的不同 复杂度不同最高可以达到 O( m*n ).   (m,n分别为两个字符串的长度) KMP算法:   我们先来看普通的暴力方法在对下面的匹配过程: 这个匹配过程到达 X,Y 处发现不匹配,按照暴力方法我们就把下面的字符串向右移动一个字符然后继续跟A进行匹配.但是实际上看图我们就可以知道移动一个字符肯定…

2015年3月20日 0条评论 0点热度 阅读全文

              Stamps 邮票问题 题目描述:  已知一个 N 枚邮票的面值集合(如,{1 分,3 分})和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。  例如,假设有 1 分和 3 分的邮票;你最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资(用 1 分邮票贴就行了),接下来的邮资也不难:  6 = 3 + 3  7 = 3 + 3…

2014年12月27日 0条评论 0点热度 阅读全文

最长不下降子序列问题即是求:一数列中某一严格单增的子序列的最长长度. 举例:6253174中最长不下降的子序列257、237、234.即是最长长度为3. 一、简单的O(N^2)算法 当我们定义问题F(i)为以bi结束的最长不下降序列时,则问题F(I) 有I-1个子问题:F(1), F(2),…, F(I-1)。我们要使F(I)最大,则要找 到一个F(j)(1≤j≤I-1)最大的子问题,且同时满足Bj < Bi,这时F(I)=F(j)max+1; 如果不存在Bj < Bi(1≤j≤I-1),那么i不存在前…

2014年11月12日 0条评论 0点热度 阅读全文

        先谈谈动态规划: 动态规划算法可分解成从先到后的4个步骤: 1. 描述一个最优解的结构; 2. 递归地定义最优解的值; 3. 以“自底向上”的方式计算最优解的值; 4. 从已计算的信息中构建出最优解的路径。 其中步骤1~3是动态规划求解问题的基础。如果题目只要求最优解的值,则步骤4可以省略。 在dd大牛的《背包九讲》中思路是这样的: 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路 …

2014年11月8日 0条评论 0点热度 阅读全文