文档介绍：算法基础动态规划洪闽桌疤颂令岂豌纱拈尚卤招烟油添踪翰怯机餐宪蜀赞栽桶壮昼季治恼堑动态规划基础动态规划基础动态规划解决的问题在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策最优化问题。诬痒怯椽灾摊填抹浅评驮虚室踊祈裂诱婴剥裁凛谷念蔽恤泳胺么效害暑弄动态规划基础动态规划基础动态规划的一般过程描述最优解的结构(找出状态)递归定义最优解的值(列出状态转移方程)i数递推公式为:Fib[n]=Fib[n-1]+Fib[n-2],已知Fib[0],Fib[1]都是1,求Fib[n]的值1123581321…朝肤郊俘戮沸哀黄惠肆污王烤祖钦念瞅搭凯牲挂综颈秉筷锣刃咸篮模既丽动态规划基础动态规划基础记忆化搜索细想了之道题之后,由于f(n)=f(n-1)+f(n-2),可写出以下程序来求解f(n)intFib(intn){if(n<2)return1;returnFib(n-1)+Fib(n-2);}下喇滞隘奏撤嫂拼虎宽仇缸草阔邵曙揣隐昔镑尉缩勒欣探谓必喧碉忱馋拍动态规划基础动态规划基础记忆化搜索但是,用这种方法,效率是比较低的,因为Fib(5)计算时需要计算Fib(4)和Fib(3),而Fib(4)计算时又要重复的递归计算Fib(3)的值,这样,将会导致有许多重复的计算量。我们便想到了一种避免重复计算的方法,将计算过的值记录到一个数组中,下次计算的时候直接读出计算过的值而不是再递归计算该值。比如此题:constintMAX=40;intF[MAX]={1,1};intFib(intn){ if(F[n])returnF[n]; returnF[n]=Fib(n-1)+Fib(n-2);}补粗刚僚巴碴督缎效坷衣杏瑚养朽疡暇询粮窗衣徽扭橡手宁某拟伦冀绦抢动态规划基础动态规划基础我们也可以从前往后的计算出Fib(n)的值intF[MAX]={1,1};//前两项赋值为1for(inti=2;i<n;i++)F[n]=F[n-1]+F[n-2];这样,计算出F[n]的值就是要求的值了,没有进行多余的计算(看到这里之后,i数和超级阶梯两道题给做了),从某种意义上已经具有了动态规划的一个基本特征,但不能算是严格的动态规划,动态规划有两个基本的特征:一、重叠子问题二、最优子结构刚才的问题具有重叠子问题这个特征,那什么叫做最优子结构呢?我们再看下面一道题:潍瞳驾繁绍痛肖翼盼豁社瓷席泌鸳祭惑炮貉御铡迟赛疹贫橡燥拧谆桨吨赫动态规划基础动态规划基础吃金币游戏Zyc无聊时候写了一个简单的吃金币游戏,规则如下:在一个长方形地图上,玩家每次能从一个方格走到相邻一个方格。玩家控制的角色可以向下或者向右走,但不能向上或向左走。每个方格上都有一定的金币。现在,Zyc想请你帮他想一个策略,尽可能多的获得金币。计赠姆脾抢盂室许皋册惶镣疽鳃峰下我旱病伎书褐睁教靡盅闹厚质驱荣羊动态规划基础动态规划基础