动态规划终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。
结果: 输出8的二项式系数: C(8,0) ———— 1 C(8,1) ———— 8 C(8,2) ———— 28 C(8,3) ———— 56 C(8,4) ———— 70 C(8,5) ———— 56 C(8,6) ———— 28 C(8,7) ———— 8 C(8,8) ———— 1 其实可以返回整个矩阵,这样就可以一次把所有的C(n , k)都计算出来。 -------------------------------------------------------------------------------------------------------------------------------------------------- 再看动态规划: 上面棕色字体标出的就是一个动态规划算法的几个关键点: 1)怎么描述问题,要把问题描述为交叠的子问题 2)交叠子问题的初始条件(边界条件) 3)动态规划在形式上往往表现为填矩阵的形式(在后面会看到,有的可以优化空间复杂度,开一个数组即可,优化也是根据递推式的依赖形式的,后面有篇文章详细说明) 4)填矩阵的方式(或者说顺序)表明了什么?--它表明了这个动态规划从小到大产生的过程,专业点的说就是递推式的依赖形式决定了填矩阵的顺序。 --------------------------------------------------------------------------------------------------------------------------------------------------- 习题8.1 决定这一章的习题都认真的做一遍 1 a,相同点是动态规划和分治法都划分为了较小规模问题的解 b,不同点是动态规划的较小子问题是交叠的,而且要存储较小子问题的解 2 a,参见代码,已实现 b,也可以按列来填矩阵(想想为什么?)---实际上这个问题就表明了再看动态规划第四点(填矩阵的方式表明了什么) 3 easy,在讲解中已多处指出 4 a, 空间效率也是nk,参见代码,或者从矩阵上也可看出 b,可以,这个问题的表明了再看动态规划第三点(优化空间复杂度) ---为什么可以优化,上面说过,可不可以优化,以及如何优化空间复杂度依赖于它的递推形式: ---从填矩阵的那张图可以看出,这个动态规划产生各项的过程(如果按行填的话)是上一行的第 i-1 项和第 i 项加起来产生下一行的第 i 项,传统上,我们从左往右填。 ---事实上,根据它的产生过程(这个产生过程依赖于递推式自身的数学特征),可以从右往左填,这样开一个数组就行,在原数组上本地不动的填数,从右往左填可 以保证一个位置在覆盖以后不会再被用到(这是由递推式的属性决定的,需要画一画才看的比较清楚)。 这样开一个K大的数组就行了,具体的实现就不写了,已经分析的很清楚了,实现也不难 --------------------------------------------------------------------------------------------------------------------------------------------------- 由以上分析,加习题,相信对于动态规划到底是什么,核心思想,具体的操作细节,以及对于动态规划的理解都加深了吧, 有2点我觉得非常重要,一是填矩阵的顺序,二是动态规划空间复杂度的优化:这2点都跟递推式的依赖关系有关(这是本质),在形式上就表现为填矩阵的时候你的 顺序要确保每填一个新位置时你所用到的那些位置(即它依赖的)要已经填好了,在空间优化上表现为当一个位置在以后还有用的时候你不能覆盖它。 这2条结论非常重要,是深刻理解动态规划的一个重要阶梯,我也是好久慢慢悟出来的,当然,它们有更professional的表述,在下一篇文章里我会贴出。 --------------------------------------------------------------------------------------------------------------------------------------------------- 再来看2道实践的习题吧,也比较简单: 9,靠,电子版的竟然跟纸质版的不太一样,电子版书上没有这个题,截不了图,抄一下吧: 问题: 国际象棋中的车可以水平的或竖直的移动,一个车要从一个棋盘的一角移到对角线的另一角,有多少种最短路径? a,用动态规划算法求解 b,用初等排列组合知识求解 b)先说b吧,这是个很简单的高中排列组合题目了,假设棋盘大小是n*n的(囧,象棋棋盘多大这个得想想才知道,就说n吧),答案是C(2n , n) a)用a方法做下吧(主要是培养下怎么去建立动态规划的递推式) 问题是从(0,0)移动到(n,n)有多少种方法?(最短路,即横n竖n,不能回退) 设C[i , j]表示从(0,0)移动到(i ,j)的方法数(描述问题,怎么去刻画C[i , j]的含义,是动态规划的一个关键点): 那么怎么才能走到(i ,j)呢,它的上一步必定是(i-1 ,j)或者(i ,j-1)-------(分析动态规划问题的逆向思维,很重要,后面要讲) 这样就将问题描述为了交叠子问题: C[i , j] = C[i -1, j] + C[i , j-1] ( C[i , j]的含义 ) 我们要求的是C[n , n] 初始条件: C[0 , j] = j j从0到n C[i , 0] = i i从0到n 即第一行第一列确定。 填矩阵的形式:可以按行也可以按列。 以上分析画个图很容易看出来。剩下的实现就很简单了。 10 第一问就是个概率题,听起来比较拗口,其实不难,属于高中概率水平: 有了递推式后,发现其实跟上一题完全一样,就是递推式里多乘了个概率值,难怪电子版省略了一个题,剩下的略 -------------------------------------------------------------------------------------------------------------------------------------------------- 非常重要: 解这两道题后,应该知道一个动态规划的设计过程是怎样的: 个人体会是动态规划的难点在于前期的设计: a)怎么描述问题,使它能表述为一个动态规划问题(具备什么特征?最有子结构,多阶段决策,思考) b)递推式的写出(逆向思维去分析或正向思维去递归),确定你要求的是哪个值 c)有了递推式可以画个矩阵的图(一般只从式子上不太容易看出来,当然,对于牛人来说可以藐视),在图中关注以下两点: 初始条件 填矩阵的顺序(即怎么去写代码控制语句) 有了这些之后,其实动态规划的代码都很简单,它的难点在于问题的描述和解决阶段,而不在于写代码的阶段,剩下的写代码基本上就是照着公式填矩阵。 -------------------------------------------------------------------------------------------------------------------------------------------------- 差点把一个重要的问题忘了: 我们来看看象棋问题的动态规划描述,它为什么可以描述为动态规划的? 关于可以描述为交叠子问题,上面分析过了, 我们再说下最有子结构和多阶段决策: 最优子结构:有准确的定义,可以参见一些资料,我自己描述下就是:在动态规划求解过程中的,子问题产生的解对于子问题来说也是一个最优解 多阶段决策:一步步的决策,无后效性,决策只依赖于当前状态,不依赖于之前的状态。 看看象棋问题的最优子结构性质:在到达终点之前的任意(i , j)点所走过的方法数都是最少的。 多阶段决策:每次决定往哪走只跟当前在哪有关,跟以前怎么走的无关。 |
|
来自: Home of heart > 《我的图书馆》