博客首页 → 动态规划

最新文章列表

动态规划（dynamic programming）

方法概述: 发展及研究内容 动态规划(dynamic programming)是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—— ...
动态规划算法dynamic programming 
静妙仙人 评论(0) 有3525人浏览 2012-10-10 12:57

最长回文子串求解

题目：给定一个字符串，求其的最大回文子串。例如：字符串：owwoshisbsiha，它的最大回文子串是：hisbsih。 求解方法：暴力枚举、动态规划、后缀数组 ...
最长回文子串求解四个方法后缀数组后缀树动态规划线性求解 
DSQiu 评论(2) 有9589人浏览 2012-09-30 08:54

一个简单的动态规划例子

动态规划 既Dynamic Programming 1）动态规划是运筹学中用于求解决策过程中的最优化数学方法。 当然，我们在这里关注的是作为一种算法设计技术，作为一种使用多阶段决策过程最优的通用方法。 它是应用数学中用于解决某类最优化问题的重要工具。 2）如果问题是由交叠的子问题所构成，我们就可以用动态规划技术来解决它，一般来说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系包含了相 ...
JAVA动态规划二项式 
aijnecJay 评论(0) 有12024人浏览 2012-09-19 14:11

最少硬币数问题

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * c1...cn个硬币，面值各不相同，现要用最少的硬币数，使得钱数为k，给出方案 * @author sky * * 设dp[i]为k为i时，最少需要的硬币个数 ...
动态规划最少硬币问题 
madbluesky 评论(1) 有1888人浏览 2012-09-03 23:09

算法-动态规划：一个数组a[0...n-1]，求a[j]-a[i]的最大值，其中i<j

其中数组a[n]是无序的，求a[j]-a[i]的最大值，且i<j，解此题有两种算法：   第一种方法：   从左往右求下标0到 k - 1 的最小值MIN从右往左求 下标k到n -1 的最大值MAX 对于每个k都有一个MAX - MIN的值，最后求这个值的最大值即可。 例如数组：4 5 2 6 3 1 K：1 2 3 4 5 MIN： 4 4 2 2 2 MAX：6 6 6  ...
动态规划 
mars914 评论(0) 有9266人浏览 2012-08-29 22:53

HDU 1421 搬寝室

/* 状态转移方程：d[i][j] = min(d[i][j - 1], d[i - 1][j - 2] + (A[j] - A[j - 1]) * (A[j] - A[j - 1])) d[i][j]:表示前j个物品搬运i次最小的疲劳度 */ #include <iostream> #include <cmath> using namespace std; const ...
动态规划 
laozhaopian68 评论(0) 有5人浏览 2012-08-18 22:04

tyvj p1096 0-1背包求种数

  在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)， 再读入N个正数（可以有相同的数字，每个数字均在1000以内）， 在这N个数中找出若干个数， 使它们的和是M， 把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。     ...
动态规划 
bingge5 评论(0) 有13人浏览 2012-08-16 22:38

POJ 4374 单调队列优化 DP

这题的转移很明显。 用dp[i][j] 表示到达i层j位置时的最大得分 sum[i][j] 表示第i层前j个数的和 dp[i][j] = max(max(dp[i - 1][j + k] + sum[i-1][j +k-1] - sum[i - 1][j - 1] + score[i][j]), max(dp[i - 1][j - k] - sum[i-1][j -k] + sum[i ...
动态规划 
bibei1234 评论(0) 有11人浏览 2012-08-16 22:01

FOJ2013-最大子段和

FOJ2013 限定子段长度最短为m,,贴个我的超时代码Time Limit Exceed 哈哈 方法和 hdu1003 一样 #include<iostream> #include<stdio.h> using namespace std; int num[1000001],n,m; int getn(int x) { int i, ...
动态规划 
yingchifei 评论(0) 有8人浏览 2012-08-13 19:57

HDOJ 1024 Max Sum Plus Plus

/*超时。题意：输出m个子序列和的最大值思路：动态规划 + 滑动数组d[m][j] = max(d[m][j - 1] + e[j], max(d[m - 1][k] + e[j]) | k ∈ [m -1, j)).表示前j个序列分割成m组，最大序列和因为状态方程中只用到d[m]和d[m - 1]两个状态，所以只需要一个二维数组即可。优化：至于max(d[m - 1][k] + e[j])过程，可 ...
动态规划 
hongqiang 评论(0) 有1038人浏览 2012-08-07 22:38

[DP]zoj 3310：Unrequited Love

大致题意：    给出一个长度为n的数字环，现在要取出某些位置的数字使得取出的数字的和最大且这些数字的位置两两不相邻。   大致思路：    要分为两种情况，取第一个和不取第一个，分别dp两次求最大值即可。   #include<iostream> #include<cstring> #include<cstdio> using namespa ...
dp动态规划acmzoj 3310bbezxcy 
暴风雪 评论(0) 有952人浏览 2012-06-19 15:21

[DP]zoj 3331：Process the Tasks

大致题意：    有两个机器a，b。要处理n个部件，第i个部件在机器a上完成需要atime[i]，在b机器上需要btime[i]，每个部件只能选择一个机器来完成。且当地i个部件开始加工时前[1，i-1]部件必须已经完成或者正在被加工。求加工完所有n个部件的最小时间是多少。   大致思路：    好神的dp，开始时乱想了几个状态都觉得不靠谱，膜拜了众犇的博客才明白怎么做，大神敬请bs。这里的状态表 ...
dp动态规划acmzoj 3331bbezxcy 
暴风雪 评论(0) 有1588人浏览 2012-06-12 11:39

关于最长递增子序列的实际应用--动态规划

参考链接： a.http://www.programfan.com/blog/article.asp?id=13086 b.http://blog.csdn.net/hhygcy/article/details/3950158   1.对（http://hao3100590.iteye.com/blog/1548135）中问题6：最长递增子序列的改进，减少时间复杂度 算法的思想：   它 ...
搭桥问题叠箱子最大递增子序列动态规划 
hao3100590 评论(0) 有1845人浏览 2012-06-07 11:35

动态规划

该文章转载自：http://www.cppblog.com/Fox/archive/2008/05/07/Dynamic_programming.html 非常感谢！ 以前在学习非数值算法的时候，曾经了解过动态规划算法（Dynamic programming），以下是对Wikipedia上动态规划的翻译，图也是Wikipedia上的，仓促行文，不到之处，请方家指正。 这篇文章的术语实在是 ...
算法动态规划 
hao3100590 评论(0) 有1452人浏览 2012-06-06 11:23

[状态压缩DP]zoj 3471：Most Powerful

大致题意：     有n颗原子，给出一个n*n的矩阵map。map[i][j]=a，则代表第i个原子和第j个相撞，且第j个原子会消失，并且释放出a的能量，现在求释放能量的最大值是多少。   大致思路：    dp[b]表示状态b下的最大能量值，比如b=10，则可以二进制转化为1010，在这里我们把0看作保留这一位的原子，1看作这一位的原子消失。则dp[10]可看作第2，4位的原子消失，其他位的 ...
状态压缩动态规划acmzoj 3471bbezxcy 
暴风雪 评论(0) 有1316人浏览 2012-06-05 17:00

[DP]zoj 3468：Dice War

大致题意：    输入a,b(a,b<=8)，求出扔a个骰子得到的数字总和大于扔b个骰子的概率。   大致思路：    很水的DP，水到我这种水人都能1A。     DP[i][j]代表投i个骰子的时候，数字为j的概率。先预处理出dp数组，等输入a,b时直接计算输出即可。   #include<iostream> #include<cstring> ...
DP动态规划zoj 3468acmbbezxcy 
暴风雪 评论(0) 有1117人浏览 2012-06-04 17:35

最长公共子序列

  最长公共子序列(动态规划解决) 其中：某个序列的子序列定义为原序列中的0个或多个元素被去掉之后剩下的元素序列。 给定两个序列 X = { x1 , x2 , … , xm } Y = { y1 , y2 , … , yn } 求X和Y的一个最长公共子序列 举例 X = { a , b , c , b , d , a , b } Y = { b , d , c , a , b , ...
最长公共子序列动态规划 
phenix_chen 评论(0) 有1093人浏览 2012-06-03 10:40

动态规划之-0-1背包问题

package cn.gao.algorithm2.service; public class Test7 { /** * @param args * 动态规划问题，0-1背包问题 * f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值 * f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[ ...
动态规划递归0-1背包分治 
爱在爪哇 评论(0) 有1548人浏览 2012-05-22 00:08

动态规划

动态规划常见题目解析： 分别为： 1.最长公共子序列 2.最大字段和 3.0-1背包问题 下面逐一描述： 1.最长公共子序列 题目描述： 例如对于X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},则序列{B,C,B,A}就是X和Y的最长公共子序列。 解法： 按照该思路的解法： #include <iostream> using namespa ...
动态规划 
yiyiboy2010 评论(0) 有1171人浏览 2012-04-19 12:51

最近博客热门TAG

Java(141741) C(73643) C++(68602) SQL(64557) C#(59604) XML(59131) HTML(59042) JavaScript(54916) .net(54782) Web(54511) 工作(54116) Linux(50906) Oracle(49861) 应用服务器(43285) Spring(40811) 编程(39452) Windows(39380) JSP(37540) MySQL(37266) 数据结构(36420)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics