博客首页 → 动态规划

最新文章列表

数学之美 二十四 从全球导航到输入法——谈谈动态规划

今年九月二十三日，Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机，其中一个重要的功能是利用全球卫星定位系统实现全球导航。 ...
动态规划全球导航输入法 
abc123456789cba 评论(0) 有1016人浏览 2012-04-13 08:56

求解最大子序列和问题

原题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大； 不想说明什么，我们数据结构老师第一节课就给我们讲这个，以前给实现过一个暴力算法版的算法复杂度O(n2)，现在实现一个动态规划版的；    /* * * 求解最大子序列和问题O(n)算法; * @param array */ public static void maxSubS ...
算法动态规划 
luliangy 评论(3) 有2507人浏览 2012-03-17 01:12

[排序+DP]hdoj 1069：Monkey and Banana

大致题意：    给你n种箱子，每种箱子都有各自的长宽高，每种箱子都有无限多个。如果一个箱子的长和宽都小于另一个箱子，那么这个箱子就可以放在那个箱子上面。求这n种箱子最多可以堆多高。   大致思路：     首先排序，按照长和宽中最长的那个。保证如果如果箱子i可以放在箱子j上面的话则j<i。然后就是简单的DP~~   #include<cstring> #incl ...
DP动态规划hdoj 1069acm数据结构 
暴风雪 评论(0) 有1747人浏览 2012-03-07 14:25

[DP 动态规划]poj 3267：The Cow Lexicon

大致题意：     给出一个长度为l的文本和一个由n个单词组成的字典。求至少从文本中去掉多少个字符才能使得这个文本全部由字典中的单词组成。   大致思路：     DP，转移方程为dp[i]=min(dp[i-1]+1,dp[pos+1]+i-pos-1-tmp);//dp[i]为前i个字符中需要去掉的字符数量。     转移的示例如下，这里文本是browndcodw 文本是cow，从st ...
DP动态规划poj 3267acm数据结构 
暴风雪 评论(0) 有2837人浏览 2012-03-02 13:38

[DP]poj 1952：BUY LOW, BUY LOWER

大致题意：     给出一列由n个数字组成的数，求出最长递减子序列的长度，并求出共有多少种最长递减子序列。   大致思路：    第一问很简单，第二问实在看不出来了，查的题解，囧啊，大家不要bs我~~大致过程就是在第一个求最长递增子序列的基础上，对于当前元素是否能够接在其他递减子序列后面再做讨论。要注意两个子序列完全相同的情况，在这里完全相同的子序列只能算一个。   #include< ...
DPpoj 1952动态规划acm数据结构 
暴风雪 评论(0) 有1699人浏览 2012-02-29 20:47

[DP] poj 2033：Alphacode

大致题意：     给出一串数，求出这串数可能组成多少种字母排列。   大致思路：     简单DP，一定要注意0的情况   #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=50000; char str[ ...
DP动态规划poj 2033acm数据结构 
暴风雪 评论(0) 有1482人浏览 2012-02-29 10:59

[DP+记忆化搜索]hdoj 1224：Free DIY Tour

大致题意：     给出一个正整数n，并给出一个由n+1个点组成的DAG，每个点有一个权值，代表走到这个点后能得到的收益值，1和n+1点的收益值是0。求出从1点走到n+1点收益值最大是多少。   大致思路：    DP，用记忆化搜索来实现。     #include<iostream> #include<cstdio> #include <algorit ...
DP记忆化搜索动态规划hdoj 1224acm 
暴风雪 评论(2) 有1512人浏览 2012-02-28 21:34

动态规划算法求解硬币找零问题

动态规划算法求解硬币找零问题   动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后 ...
动态规划 
xsjleilei 评论(0) 有2166人浏览 2012-02-28 16:03

最大子序列和

问题： 给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。 输入： 第一行为一个正整数N，第二行为N个整数，表示序列中的数。 输出： 输入可能包括多组数据，对于每一组输入数据， 仅输出一个数，表示最大序列和。 ...
动态规划最大子序列和 
YuHuang.Neil 评论(0) 有1279人浏览 2012-02-15 14:06

寻找最长回文串长度的一个动态规划解法

今天某面试题，要在任意给定的字符串中，寻找最长回文串的长度。 注：回文串是指abc、abbc、aaabccc、aaaccc这种左右对称的字符串。 比如：abcaabbbaad字符串中，最长回文串的长度是7。   /** * 思路：<br> * 动态规划。一个指针从头往后遍历；一个指针从后往前遍历，把之前比较过的结果存到二维数组内，每个单元表示截止匹配到某一个字符串，所属的 ...
回文动态规划算法 
RayChase 评论(0) 有8729人浏览 2012-01-05 22:03

斐波那契数：动态规划法和分治法

这个学期开了一门叫算法的课，为了今天的ＩＴＡＴ复赛，这两天研究了一下这门课。感觉算法真的是太神奇了。就比如说今天学了动态规划（小小的入门）。用它实现了斐波那契数，和原来的用分治法的一比较，差距出来了。相差十几几万倍（要算的数越大相差的倍数越多）。下面是实现： #include <iostream> #include <ctime> using namespace ...
算法斐波那契数动态规划分治法 
zeng1990 评论(0) 有5052人浏览 2011-11-05 10:48

动态规划之最优二叉查找树源代码——算法导论

此算法是根据《算法导论》里面的介绍编写的。数据也是。代码运行后，结果数据正确。   以《算法导论》P213中未测试数据： p[6]={-100,0.15,0.1, ...
动态规划最优二叉查找树源代码算法导论 
shinepengwei 评论(0) 有2373人浏览 2011-10-16 20:24

【动态规划】sicily1163

  1163. Tour 题目大意： 就是一个双调旅程问题，从最左边的点走到最右边的点，然后从最右边走回最左边，问这段旅程的最短距离。   解题思路： 题目已经告诉我们，所有的点已经按照左到右的顺序输入了。 题目可以转换成，从第一个点出发，分两路A，B走，最后汇集到第n个点。 用动态规划： dp[i][j]表示A到达i点，B到达j点时的最短路径。我们始终考虑i> ...
算法sicily动态规划 
rapheal 评论(0) 有1412人浏览 2011-09-24 13:58

【动态规划】sicily1221

  1221. 数字游戏 解题思路： 题目有个地方，我理解错了，导致WA很多次，问题是当你擦除a[i]时，你要将它对应的b[i]去减剩余的序列，之前一直以为第i轮就减去b[i]，ORZ。 简单的动态，dp[i]表示去到第i轮时的最大擦出和。 按照我们直观的思路，肯定是最大消费的（也就是b[i]比较大的）应该先拿掉，因此我们先按照cost排序。 dp[j] = min{dp[j-1 ...
算法动态规划sicily 
rapheal 评论(0) 有1618人浏览 2011-09-23 16:13

【动态规划】sicily1001

1001. Alphacode   题目大意： 将一串字符串（只有A-Z）转化成数字0-9，转换的规则：A->1，B->2 ......Z->26。 那么从这段数字再转换回去字符串就会发生一些歧义，题目要求求出一段数字转换成字符串的最多数量。   解题思路： 如果说用dp[i]表示当前的前i个数字能够转化的字符串数量，当str[i+1]加进 ...
算法sicily动态规划 
rapheal 评论(0) 有1919人浏览 2011-09-23 15:36

【动态规划】sicily1011

1011. Lenny's Lucky Lotto 题目大意： 给定正整数n, m，构建的列表满足下列条件： 列表长度为n 列表的第i个数不能超过2的i次方 列表的最后一个数不能超过m 求出这样的列表的最大数目。   解题思路： 一般遇到需要求最优解的，应该立马想到动态规划； 影响列表的数目的应该是有两个状态，一个是列表的长度，一个是列表的末 ...
算法动态规划sicily 
rapheal 评论(0) 有1458人浏览 2011-09-23 01:58

hdu 2577 How to Type（很爽很好玩的DP）

How to Type Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 842    Accepted Submission(s): 364 Problem Description Pirates have finished devel ...
动态规划DPACM算法数据结构 
gzhu_101majia 评论(0) 有1835人浏览 2011-08-27 21:46

hdu 2571 命运

命运 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2499    Accepted Submission(s): 893 Problem Description 穿过幽谷意味着离大魔王lemon已经无限接近了！可谁能想到，yifen ...
动态规划DPACM算法数据结构 
gzhu_101majia 评论(0) 有979人浏览 2011-08-27 21:34

hdu 2084 数塔（最基础最简单的DP）

 数塔 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7404    Accepted Submission(s): 4412 Problem Description 在讲述DP算法的 ...
DP动态规划ACM算法数据结构 
gzhu_101majia 评论(0) 有1374人浏览 2011-08-27 21:26

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics