教你彻底学会动态规划——入门篇
&&& 动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例子来一步一步讲解动态规划是怎样使用的，只有知道怎样使用，才能更好地理解，而不是一味地对概念和原理进行反复琢磨。
&&& 首先，我们看一下这道题（此题目来源于北大POJ）：
&&& 数字三角形(POJ1163)
在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99
&&& 输入格式：
&&& 5&&&&& //表示三角形的行数&&& 接下来输入三角形
&&& 8&& 1&& 0
&&& 2&& 7&& 4&& 4
&&& 4&& 5&& 2&& 6&& 5
&&& 要求输出最大和
&&& 接下来，我们来分析一下解题思路：
&&& 首先，肯定得用二维数组来存放数字三角形
&&& 然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)
&&& 我们用MaxSum(r, j)表示从D(r,j)到底边的各条路径中，最佳路径的数字之和。
&&& 因此，此题的最终问题就变成了求 MaxSum(1,1)
&&& 当我们看到这个题目的时候，首先想到的就是可以用简单的递归来解题：
&&& D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形，我们可以写出如下的递归式：&&&
if ( r == N)
MaxSum(r,j) = D(r,j)
MaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j)
&&& 根据上面这个简单的递归式，我们就可以很轻松地写出完整的递归代码：&
#include &iostream&
#include &algorithm&
#define MAX 101
int D[MAX][MAX];
int MaxSum(int i, int j){
return D[i][j];
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
return max(x,y)+D[i][j];
int main(){
for(i=1;i&=n;i++)
for(j=1;j&=i;j++)
cin && D[i][j];
cout && MaxSum(1,1) &&
&&& 对于如上这段递归的代码，当我提交到POJ时，会显示如下结果：
&&& 对的，代码运行超时了，为什么会超时呢？
&&& 答案很简单，因为我们重复计算了，当我们在进行递归时，计算机帮我们计算的过程如下图：
&&& 就拿第三行数字1来说，当我们计算从第2行的数字3开始的MaxSum时会计算出从1开始的MaxSum，当我们计算从第二行的数字8开始的MaxSum的时候又会计算一次从1开始的MaxSum，也就是说有重复计算。这样就浪费了大量的时间。也就是说如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2的n次方,对于 n = 100 行，肯定超时。&
&&& 接下来，我们就要考虑如何进行改进，我们自然而然就可以想到如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用n方的时间复杂度完成计算。因为三角形的数字总数是 n(n+1)/2
&&& 根据这个思路，我们就可以将上面的代码进行改进，使之成为记忆递归型的动态规划程序：&
#include &iostream&
#include &algorithm&
#define MAX 101
int D[MAX][MAX];
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
if( maxSum[i][j] != -1 )
return maxSum[i][j];
maxSum[i][j] = D[i][j];
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
maxSum[i][j] = max(x,y)+ D[i][j];
return maxSum[i][j];
int main(){
for(i=1;i&=n;i++)
for(j=1;j&=i;j++) {
cin && D[i][j];
maxSum[i][j] = -1;
cout && MaxSum(1,1) &&
&&& 当我们提交如上代码时，结果就是一次AC
&&& 虽然在短时间内就AC了。但是，我们并不能满足于这样的代码，因为递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，我们现在就要考虑如何把递归转换为递推，让我们一步一步来完成这个过程。
&&&&我们首先需要计算的是最后一行，因此可以把最后一行直接写出，如下图：
&&& 现在开始分析倒数第二行的每一个数，现分析数字2，2可以和最后一行4相加，也可以和最后一行的5相加，但是很显然和5相加要更大一点，结果为7，我们此时就可以将7保存起来，然后分析数字7，7可以和最后一行的5相加，也可以和最后一行的2相加，很显然和5相加更大，结果为12，因此我们将12保存起来。以此类推。。我们可以得到下面这张图：
&&& 然后按同样的道理分析倒数第三行和倒数第四行，最后分析第一行，我们可以依次得到如下结果：
&&& 上面的推导过程相信大家不难理解，理解之后我们就可以写出如下的递推型动态规划程序：&
#include &iostream&
#include &algorithm&
#define MAX 101
int D[MAX][MAX];
int maxSum[MAX][MAX];
int main(){
for(i=1;i&=n;i++)
for(j=1;j&=i;j++)
cin && D[i][j];
for( int i = 1;i &= ++ i )
maxSum[n][i] = D[n][i];
for( int i = n-1; i&= 1;
for( int j = 1; j &= ++j )
maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];
cout && maxSum[1][1] &&
&&&&&我们的代码仅仅是这样就够了吗？当然不是，我们仍然可以继续优化，而这个优化当然是对于空间进行优化，其实完全没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。
&&&& 对于空间优化后的具体递推过程如下：
&&& 接下里的步骤就按上图的过程一步一步推导就可以了。进一步考虑，我们甚至可以连maxSum数组都可以不要，直接用D的第n行直接替代maxSum即可。但是这里需要强调的是：虽然节省空间，但是时间复杂度还是不变的。
&&& 依照上面的方式，我们可以写出如下代码：&&&&
#include &iostream&
#include &algorithm&
#define MAX 101
int D[MAX][MAX];
int * maxS
int main(){
for(i=1;i&=n;i++)
for(j=1;j&=i;j++)
cin && D[i][j];
maxSum = D[n]; //maxSum指向第n行
for( int i = n-1; i&= 1;
for( int j = 1; j &= ++j )
maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];
cout && maxSum[1] &&
&&& 接下来，我们就进行一下总结：
&&& 递归到动规的一般转化方法
&&& 递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。
&&& 动规解题的一般思路
&&& 1. 将原问题分解为子问题
&&& 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。&&& 子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。
&&& 2.确定状态
&&& 在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状 态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状 态”所对应的子问题的解。&&& 所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个问题的状态空间里一共就有N×(N+1)/2个状态。
&&& 整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。
&&& 3.确定一些初始状态（边界状态）的值
&&&&以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值。
&&&&4. 确定状态转移方程
&&&& 定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。
&&& 数字三角形的状态转移方程:
&&& 能用动规解决的问题的特点
&&& 1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。
&&& 2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？&>&java源代码n个数里找最大的k个
java源代码n个数里找最大的k个
上传大小：5KB
Java源代码，n个数里找最大的k个，堆排序
综合评分：0（0位用户评分）
所需积分：
下载个数：15
{%username%}回复{%com_username%}{%time%}\
/*点击出现回复框*/
$(".respond_btn").on("click", function (e) {
$(this).parents(".rightLi").children(".respond_box").show();
e.stopPropagation();
$(".cancel_res").on("click", function (e) {
$(this).parents(".res_b").siblings(".res_area").val("");
$(this).parents(".respond_box").hide();
e.stopPropagation();
/*删除评论*/
$(".del_comment_c").on("click", function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_invalid/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parents(".conLi").remove();
alert(data.msg);
$(".res_btn").click(function (e) {
var q = $("#form1").serializeArray();
console.log(q);
var res_area_r = $.trim($(".res_area_r").val());
if (res_area_r == '') {
$(".res_text").css({color: "red"});
$.post("/index.php/comment/do_comment_reply/", q,
function (data) {
if (data.succ == 1) {
var $target,
evt = e || window.
$target = $(evt.target || evt.srcElement);
var $dd = $target.parents('dd');
var $wrapReply = $dd.find('.respond_box');
console.log($wrapReply);
var mess = $(".res_area_r").val();
var str = str.replace(/{%header%}/g, data.header)
.replace(/{%href%}/g, 'http://' + window.location.host + '/user/' + data.username)
.replace(/{%username%}/g, data.username)
.replace(/{%com_username%}/g, _username)
.replace(/{%time%}/g, data.time)
.replace(/{%id%}/g, data.id)
.replace(/{%mess%}/g, mess);
$dd.after(str);
$(".respond_box").hide();
$(".res_area_r").val("");
$(".res_area").val("");
$wrapReply.hide();
alert(data.msg);
}, "json");
/*删除回复*/
$(".rightLi").on("click",'.del_comment_r', function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_comment_del/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parent().parent().parent().parent().parent().remove();
$(e.target).parents('.res_list').remove()
alert(data.msg);
//填充回复
function KeyP(v) {
$(".res_area_r").val($.trim($(".res_area").val()));
评论共有0条
审核通过送C币
Java优质资源
创建者：circle__gossoon
学习java会用到的jar包集锦
创建者：qq_
创建者：baiyunxiaoxiao_chen
上传者其他资源上传者专辑
《Deep Learning》谷歌科学家Yoshua Bengio等
豆瓣图书数据
开发技术热门标签
VIP会员动态
前端开发重难点
17年软考最新真题及解析
物联网全栈开发专题
二十大技术领域优质资源
spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip
CSDN&VIP年卡&4000万程序员的必选
java源代码n个数里找最大的k个
会员到期时间：
剩余下载个数：
剩余C币：0
剩余积分：6726
积分不足！
资源所需积分
当前拥有积分
您可以选择
程序员的必选
绿色安全资源
资源所需积分
当前拥有积分
当前拥有C币
(仅够下载10个资源)
全站1200个资源免积分下载
资源所需积分
当前拥有积分
当前拥有C币
全站1200个资源免积分下载
资源所需积分
当前拥有积分
当前拥有C币
您的积分不足，将扣除 10 C币
全站1200个资源免积分下载
你当前的下载分为234。
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
java源代码n个数里找最大的k个博客访问： 679488
博文数量： 170
博客积分： 3017
博客等级： 少校
技术积分： 3829
注册时间：
Now in Baidu WISE team
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
【问题描述】
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
【输入文件】
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2&=N&=15, 0&=K&=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。
【输出文件】
输出文件仅一行包含一个整数，表示要求的最大的结果
【输入输出样例】
题目分析：
Step 1:我们先考虑简单的情况，假设题目的输入是只有1个乘号。
对于1,2,3,4,5这个序列Q，在插入1个乘号的情况下，乘号的位置依次有4个。且乘号将这个序列分成了两部分，我们记为left,right。
显然，序列的计算值为left*right。
left:1&&&&&&&&&&&&&&&& right: 2+3+4+5
left:1+2&&&&&&&&&&&&&& right: 3+4+5
left:1+2+3&&&&&&&&&&&& right: 4+5
left:1+2+3+4&&&&&&&&&& right: 5
我们只需枚举出所有情况，记录最大值即可
记录这个过程为f(Q)
Step 2:我们再考虑增加一个乘号的情况。
增加一个乘号的时候，我们假设第一个乘号位置固定在数字1后面，与上面一种情况相比，不考虑乘号的时候
left:1&&&&&&&&&&&&&&&& right: 2+3+4+5
right是简单求和即可。
因为第一个乘号位置固定，我们只能在right序列中插入第二个乘号。我们对right序列再执行一遍上一步操作，就得到了序列(2,3,4,5)中插入1个乘号的最大值。记录右边序列为Qr,此时
left:1&&&&&&&&&&&&&&&& right: f(Qr) (Qr = (2,3,4,5))
那么，如果有一个乘号在数字1后面， 算式的最大值就是 1*f(Qr)
Step 3:同样的方法，我们可以计算固定第一个乘号的位置其他3种情况
left:1+2&&&&&&&&&&&&&& right: f(Qr) (Qr = (3,4,5))
left:1+2+3&&&&&&&&&&&& right: f(Qr) (Qr = (4,5))
left:1+2+3+4&&&&&&&&&& right: f(Qr) (Qr = (5))
Step 4: 记录下这4种情况的算式最大值，就可以得到一个最终答案
根据以上分析，我们可以得出一个状态转移方程
记输入序列为Q,
S(Q,start,len)表示在序列Q中，从start位置开始长度为len的序列的和(即上面分析中的left)。
f(Q,start,len,mulcount)表示在序列Q中，从start位置开始长度为len的序列，向其中插入mulcount个乘号的最大算式值(即上面分析中的right)。
f(Q,start,len,mulcount) = max{ S(Q,start,leftlen) * f(Q, leftlen,len-leftlen, mulcount-1) | 0&leftlen&len-1 }
下面给出了一个示意的递归代码(非最优)。codepad.org已验证通过。可以改为迭代代码。
代码优化：
1.可使用数组存储代替计算序列和的过程
2.每次计算出f(...)值，可直接使用2维数组存储，用来替代22行的递归调用。
#include &stdio.h&
#include &stdlib.h&
#include &assert.h&
#define MAX 16
int getsum(int *nums, int start, int end){
&&&&assert(nums!=NULL && start&=end);
&&&&int sum = 0;
&&&&int i;
&&&&for(i = start; i&=end; i++)
&&&&&&&&sum+=nums[i];
&&&&return sum;
int test(int * nums, int start, int len, int mulcount){
&&&&if(mulcount == 0)
&&&&&&&&return getsum(nums, start, start+len-1);
&&&&int m = 1;
&&&&int midd[MAX];
&&&&int loc = start;
&&&&int max = 0;
&&&&for(;loc-start&len-1;loc++){
&&&&&&&&midd[loc] = getsum(nums,start,loc) * test(nums, loc+1, start+len-loc-1, mulcount-1);
&&&&&&&&max = max&midd[loc] ? midd[loc]:max;
&&&&return max;
int main(){
&&&&int nums[] = {1,2,3,4,5};
&&&&int mulcount = 2;
&&&&int max = test(nums, 0, sizeof(nums)/sizeof(int), mulcount);
&&&&printf("%d n", max);
阅读(3466) | 评论(0) | 转发(1) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。}