动态规划快速入门手册V0.10.docVIP

动态规划快速入门手册 前言： 准备知识：基础C语言，递归。 写给小朋宇看的手册，大牛神牛无视。 制作粗糙。觉得我写的好，那就帮我修改维护完善（比如说帮我弄一下图片或者排版之类的）之后发给我，或者扔到网上之类的。 目前只写到了0.10。还有目前按计划还有一章待写，是递推的艺术。 转载注不注明出处随你，标个自己的ID上去我也懒得管。 一 分裂和征服 分治的全称是分而治之。治取“处理”之义。据说来源于战国时的合纵连横。秦王朝想统一天下，但是灭掉六个国家是一个很难的问题。于是秦国采取联盟其中的一个国家，然后灭掉另外的国家的策略来分解这个大问题。这种把大问题分解为小问题，然后分别处理的做法，被称为分治。 分治是一种几千年来一直行之有效的思维方法。这其间包含着人类最初的哲学思考和信仰：人怎样能两次踏进同一河流？世上哪有两片相同的树叶？面对纷繁芜杂的世界，人类又要如何应对？“万物源于水。”古希腊先哲泰勒斯的断言也许幼稚可笑，但其中包含的思想——复杂由简单组成，却是人类几千年不改的信念。“物理上真实的东西一定是逻辑上简单的东西。（爱因斯坦）”谁又能证明世界背后一定存在着规律？人类又如何逃脱缸中之脑的诅咒？但是，我们别无选择。如果否认世界的简单和规律，人类又如何认识世界？ 认识世界，我们从复杂中寻找简单；解决问题，我们也同样把复杂的问题分解为简单的问题。也许对于秒针来说，一天摆动是八万多次是一个巨大的难题，但是如果把问题分解为一秒摆动一次的子问题，似乎就很轻松了呢。也许过一千题听上去很困难，但是把它分解为每天做三题的子问题，似乎就觉得可以完成了。成功学上把大目标分解为小目标的方法，用的正是分治的思想。还有数学上的分类讨论，以及那个如何把大象装进冰箱的笑话，都蕴含着分治的思想。 回到算法问题上来。如果我们能把复杂的问题分解为性质相同的子问题然后递归处理，复杂的问题就迎刃而解了。 比如说，求解斐波拉契数列。由于F[I]=F[I-1]+F[I-2]（F[1]=1,F[2]=1），我们可以通过递推公式把求F[N]的问题转化为求解F[N-1]，F[N-2]的问题。这好像把问题变复杂了，因为我们需要多求解一个问题了。但是，一个更关键的改变是，问题的规模变小了！既然我们可以把N转化为N-1，那么N-1不就能转化为N-2了么？这样转化下去，最终问题会归为求解若干F[1]和F[2]之和。F[1]和F[2]那还不简单，就是1啊，那么我们要做的就是求解若干个1+1。复杂的问题就这样变得简单了。 图1 F[4]的递归过程 基于以上分析，我们可以很简单地写出递归程序： Int f(int i) { If (i=2) return 1; Else return f(i-1)+f(i-2); } 有人会说，我由F[1]，F[2]算出F[3]，然后算出F[4]，直到算出F[N]，问题就解决了啊。不错，但是我想要说明的是，分治的思想。 分治并不是本文的重点，这里就一笔带过。关于分治，快速排序还有汉诺塔是更好和经典的例子。还有很重要的一点，一般来说，用分治法解题，是指没有重叠子问题的分治解法。关于重叠子问题，我接下来会说。 二 记忆的帽子戏法 思考我们刚才写下的程序。求解F[N]的时候求解了F[N-2]，然后求解F[N-1]时又求解了一次F[N-2]（比如图1中的两个2）。 我们做了重复的事情，怎么优化呢。很简单，我们开个数组，记录是否被求解没有，如果已经求解直接返回即可。我们把程序改为： Int f(int i) { If (d[i]!=-1) return d[i];//d[i]表示斐波拉契数列第i项的值，初始值均为-1，-1表示这个值还未被算出。 If (i=2) d[i]=1; Else d[i]=f(i-1)+f(i-2); Return d[i]; } 这个优化效果如何呢？想想我们原来的算法，只有在问题规模缩小到1或2的时候才终止递归，而F[1]和F[2]的值都为1，也就是说，算出来的那项有多大，我们就至少递归了那么多次！而F[36]就已经突破一千万了，若要求解更大的项即使是计算机也不能迅速出解！如果我们把结果记住呢？那么会少于2*N次递归。也就是说，F[36]只需要不到一百次递归就能出解！仅仅因为我们能记住答案！ 图2 F[6]直接递归过程 （14次递归） 图3 记忆后F[6]的递归过程 （8次递归） 仔细想想，记忆是一种很神奇东西。我们平时说某某人很有经验，说的不就是这人脑中存储了很多问题的解，能直接调用记忆解决面临的实际问题么！我们人类为什么要写一堆又一堆的书？很多不就是为了把我们已经解决过的问题记录下来么！为什么我们人类能不断进步？正是因为我们直接学习后人的总结，免去了发现过程中的困难和艰辛！说到这里，大家就不难理解为什么造纸术和印刷术是四大发明吧？