《July_algorithm 7.贪心法和动态规划.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 7.贪心法和动态规划.pdf（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、贪心法和动态规划七月算法邹博2015年11月7日10月算法在线班2/65主要内容动态规划和贪心的认识工具：马尔科夫过程贪心法Prim算法Kruskal算法Dijkstra算法动态规划最长递增子序列LIS矩阵连乘的最少乘法字符串的交替连接走棋盘/格子取数问题及其应用带陷阱的走棋盘问题两次走棋盘问题Catalan数简介10月算法在线班3/65Palindrome Partitioning所有划分 给定一个字符串str，将str划分成若干子串，使得每一个子串都是回文串。计算str的所有可能的划分。单个字符构成的字符串，显然是回文串；所以，这个的划分一定是存在的。如：s=“aab”，返回“aa”，“b
2、”；“a”，“a”，“b”。10月算法在线班4/65回文划分问题Palindrome Partitioning 思考：若当前计算得到了str0i-1的所有划分，可否添加strij，得到更大的划分呢？显然，若strij是回文串，则可以添加。剪枝：在每一步都可以判断中间结果是否为合法结果。回溯+剪枝如果某一次发现划分不合法，立刻对该分支限界。一个长度为n的字符串，最多有n-1个位置可以截断，每个位置有两种选择，因此时间复杂度为O(2n-1)=O(2n)。10月算法在线班5/65Code10月算法在线班6/65继续思考：动态规划 如果已知：str0i-1的所有回文划分(i)，如何求str0i的所有划
3、分呢？如果子串strji是回文串，则将该子串和(j-1)共同添加到(i+1)中。算法：将集合(i+1)置空；遍历j(0ji)，若strj,j+1i是回文串，则将strji，(j-1)添加到(i+1)中；i从0到n，依次调用上面两步，最终返回(n)即为所求。10月算法在线班7/65Code10月算法在线班8/65Code split10月算法在线班9/65Code split10月算法在线班10/65Palindrome Partitioning思考 与之类似的：给定仅包含数字的字符串，返回所有可能的有效IP地址组合。如：“25525511135”，返回“255.255.11.135”，“255
4、.255.111.35”。该问题只插入3个分割位置。只有添加了第3个分割符后，才能判断当前划分是否合法。如：2.5.5.25511135，才能判断出是非法的。当然，它可以通过“25511135”大于“255.255”等其他限界条件“事先”判断。10月算法在线班11/65DFS与DP深刻认识 DFS的过程，是计算完成了str0i的切分，然后递归调用，继续计算stri+1,i+2n-1的过程；而DP中，假定得到了str0i-1的所有可能切分方案，如何扩展得到str0i的切分；上述两种方法都可以从后向前计算得到对偶的分析。从本质上说，二者是等价的：最终都搜索了一颗隐式树。DFS显然是深度优先搜索的过
5、程，而DP更像层序遍历的过程。如果只计算回文划分的最少数目，动态规划更有优势；如果计算所有回文划分，DFS的空间复杂度比DP略优。10月算法在线班12/65认识论 认识事物的方法：概念、判断、推理 推理中，又分为归纳、演绎。重点考察归纳推理的具体方法。形式化表述：已知：问题规模为n的前提A 求解/求证：未知解B/结论B 记号：用An表示“问题规模为n的已知条件”10月算法在线班13/65对归纳推理的理解 若将问题规模降低到0，即已知A0，很容易计算或证明B，则有：A0B 同时，考察从A0增加一个元素，得到A1的变化过程。即：A0A1；进一步考察A1A2，A2A3AiAi+1这种方法是(严格的)
6、归纳推理，常常被称作数学归纳法。此时，由于上述推导往往不是等价推导(Ai和Ai+1不是互为充要条件)，导致随着i的增加，有价值的前提信息越来越少；为避免这一问题，采取如下方案：A1A2，A1A2A3 A1A2AiAi+1相对应的，修正后的方法依然是(严格的)归纳推理，有时被称作第二数学归纳法。10月算法在线班14/65对归纳推理的理解基本归纳法：对于Ai+1，只需考察前一个状态Ai即可完成整个推理过程，它的特点是只要状态Ai确定，则计算Ai+1时不需要考察更前序的状态A1Ai-1，在图论中，常常称之为马尔科夫模型；高阶归纳法：相应的，对于Ai+1，需考察前i个状态集A1A2Ai-1Ai才可完成
7、整个推理过程，往往称之为高阶马尔科夫模型；在计算机算法中，高阶马尔科夫模型的推理，叫做“动态规划”，而马尔科夫模型的推理，对应“贪心法”。10月算法在线班15/65以上理解的说明 无论动态规划还是贪心法，都是根据A0i计算Ai+1的过程计算Ai+1不需要Ai+2、Ai+3，一旦计算完成Ai+1，再后面计算Ai+2、Ai+3时，不会更改Ai+1的值。这即无后效性。亦可以如下理解动态规划：计算Ai+1只需要知道A0i的值，无需知道A0i是通过何种途径计算得到的只需知道它们当前的状态值本身即可。如果将A0i的全体作为一个整体，则可以认为动态规划法是马尔科夫过程，而非高阶马尔科夫过程。10月算法在线班
8、16/65贪心法 根据实际问题，选取一种度量标准。然后按照这种标准对n个输入排序，并按序一次输入一个量。如果输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。这一处理过程一直持续到n个输入都被考虑完毕，则记入最优解集合中的输入子集构成这种量度意义下的问题的最优解。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。10月算法在线班17/65最小生成树MST 最小生成树要求从一个带权无向连通图中选择n1条边并使这个图仍然连通(也即得到了一棵生成树)，同时还要考虑使树的权最小
9、。为了得到最小生成树，人们设计了很多算法，最著名的有Prim算法和Kruskal算法，这两个算法都是贪心算法。Prim算法：从某个(任意一个)结点出发，选择与该结点邻接的权值最小的边；随着结点的不断加入，每次都选择这些结点发出的边中权值最小的：重复n-1次。Kruskal算法：将边按照权值递增排序，每次选择权值最小并且不构成环的边，重复n-1次。10月算法在线班18/65最短路径 将Prim算法稍做调整，就得到Dijkstra最短路径算法：结点集V初始化为源点S一个元素：V=S，到每个点的最短路径的距离初始化为distu=graphSu；选择最小的distu：记distv是最小的，则v是当前找
10、到的不在V中且距离S最近的结点，更新V=Vv，调整distu=mindistu,distv+graphvu；重复n-1次。10月算法在线班19/65贪心法的思考 可以看到，在从Ai到Ai+1的扩展过程中，上述三个算法都没有使用A0i-1的值。往往看名字，认为它很简单；事实上，贪心法其实并不轻松，它需要严格证明一定与更先序的值无关。思考：从1元、2元、5元的纸币，问给定总价值N元，最少需要几张纸币？10月算法在线班20/65最长递增子序列LIS Longest Increasing Subsequence 给定一个长度为N的数组，找出一个最长的单调递增子序列(不一定连续，但是顺序不能乱)。例如：
11、给定一个长度为6的数组A5，6，7，1，2，8，则其最长的单调递增子序列为5，6，7，8，长度为4。分析：其实此LIS问题可以转换成最长公子序列问题，为什么呢？10月算法在线班21/65附：使用LCS解LIS问题 原数组为A 5，6，7，1，2，8 排序后：A1，2，5，6，7，8 因为，原数组A的子序列顺序保持不变，而且排序后A本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A的最长公共子序列。10月算法在线班22/65前缀分析“1”：1“14”：14“146”：146“1462”：146“14628”：146
12、8“146289”：14689“1462897”：1468910月算法在线班23/65最长递增子序列LIS记号 长度为N的数组记为A=a0a1a2.an-1；记A的前i个字符构成的前缀串为Ai=a0a1a2.ai-1，以ai结尾的最长递增子序列记做Li，其长度记为bi；假定已经计算得到了b0,1,i-1，如何计算bi呢？已知L0 L1Li-1的前提下，如何求Li？10月算法在线班24/65求解LIS 根据定义，Li必须以ai结尾；如果将ai分别缀到L0 L1Li-1后面，是否允许呢？如果aiaj，则可以将ai缀到Lj的后面，得到比Lj更长的字符串。从而：bi=max(bj)+1,0ji且aja
13、i 计算bi：遍历在i之前的所有位置j，找出满足条件ajai的最大的bj+1；计算得到b0n-1后，遍历所有的bi，找出最大值即为最大递增子序列的长度。时间复杂度为O(N2)。10月算法在线班25/65LIS的思考 思考：如何求最大递增子序列本身？记录前驱10月算法在线班26/65Code110月算法在线班27/65LIS Code split10月算法在线班28/65O(NlogN)的最长递增子序列算法 对于数组A=1,4,6,2,8,9,7 1 1,4 1,4,6 1,2,6 1,2,6,8 1,2,6,8,9 1,2,6,7,910月算法在线班29/65Code210月算法在线班30/6
14、5矩阵乘积 根据矩阵相乘的定义来计算 C=AB，需要m*n*s次乘法。三个矩阵A、B、C的阶分别是a0a1,a1a2,a2a3，从而(AB)C和A(BC)的乘法次数是a0a1a2+a0a2a3、a1a2a3+a0a1a3，二者一般情况是不相等的。问：给定n个矩阵的连乘积：A1A2A3An，如何添加括号来改变计算次序，使得乘法的计算量最小？此外：若A、B都是n阶方阵，C的计算时间复杂度为O(n3)问：可否设计更快的算法？答：分治法：Strassen分块理论意义大于实践意义。10月算法在线班31/65矩阵连乘的提法 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。考察
15、该n个矩阵的连乘积：A1A2A3An，确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的乘法次数最少。即：利用结合律，通过加括号的方式，改变计算过程，使得数乘的次数最少。10月算法在线班32/65分析 将矩阵连乘积记为Ai:j，这里ij 显然，若i=j，则Ai:j即Ai本身。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应的完全加括号方式为 计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量jiiAAA.1).)(.(211jkkkiiAAAAAA10月算法在线班33/65最优子结构 特征：
16、计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。最优子结构性质是可以使用动态规划算法求解的显著特征。10月算法在线班34/65状态转移方程 设计算Ai:j(1ijn)所需要的最少数乘次数为mi,j，则原问题的最优值为m1,n；记Ai的维度为 当i=j时，Ai:j即Ai本身，因此，mi,i=0；(i=1,2,n)当ij时，从而：jkipppjkmkimjim1,1,iipp1jipppjkmkimjijimjki,1,min0,1jki).)(.(211jkkkiiAAAAAA10
17、月算法在线班35/65矩阵连乘问题从算法到实现 由mi,j的递推关系式可以看出，在计算mi,j时，需要用到mi+1,j，mi+2,jmj-1,j；因此，求mi,j的前提，不是m0i-1;0j-1，而是沿着主对角线开始，依次求取到右上角元素。因为mi,j一个元素的计算，最多需要遍历n-1次，共O(n2)个元素，故算法的时间复杂度是O(n3)，空间复杂度是O(n2)。jipppjkmkimjijimjki,1,min0,1jki10月算法在线班36/65Code10月算法在线班37/65找零钱 给定某不超过100万元的现金总额，兑换成数量不限的100、50、10、5、2、1的组合，共有多少种组合呢
18、？10月算法在线班38/65该问题的思考过程 此问题涉及两个类别：面额和总额。如果面额都是1元的，则无论总额多少，可行的组合数显然都为1。如果面额多一种，则组合数有什么变化呢？定义dpij：使用面额小于等于i的钱币，凑成j元钱，共有多少种组合方法。dp100500=dp50500+dp100400 dpij=dpismallj+dpij-i不考虑j-i下溢出等边界问题10月算法在线班39/65递推公式 dpij=dpismallj+dpij-i 使用dom=1,2,5,10,20,50,100表示基本面额，i的意义从面额变成面额下标，则：dpij=dpi-1j+dpij-domi 从而：初始条
19、件：,1,1idomjjidpidomjidomjidpjidpjidp1010idpjdp10月算法在线班40/65Code10月算法在线班41/65滚动数组 将状态转移方程去掉第一维，很容易使用滚动数组，降低空间使用量。原状态转移方程：滚动数组版本的状态转移方程：,1,1idomjjidpidomjidomjidpjidpjidp,idomjidomjdpjlastjdp10月算法在线班42/65Code210月算法在线班43/65总结与思考 请问：本问题的时间复杂度是多少？在动态规划的问题中，如果不求具体解的内容，而只是求解的数目，往往可以使用滚动数组的方式降低空间使用量（甚至空间复杂度
20、）由于滚动数组减少了维度，甚至代码会更简单 思考0-1背包问题和格子取数问题。10月算法在线班44/65走棋盘/格子取数 给定mn的矩阵，每个位置是一个非负整数，从左上角开始，每次只能朝右和下走，走到右下角，求总和最小的路径。10月算法在线班45/65状态转移方程 走的方向决定了同一个格子不会经过两次。若当前位于(x,y)处，它来自于哪些格子呢？dp0,0=a0,0/第一行(列)累积 dpx,y=min(dpx-1,y+ax,y,dpx,y-1+ax,y)即：dpx,y=min(dpx-1,y,dpx,y-1)+ax,y 思考：若将上述问题改成“求从左上到右下的最大路径”呢？10月算法在线班4
21、6/65状态转移方程 状态转移方程：滚动数组：1,min00jichessjdpjdpjdpkchessjdpjk1,1min,0,000,00jichessjidpjidpjidpkchessjdpkchessidpjkik10月算法在线班47/65Code10月算法在线班48/65GIS中的应用10月算法在线班49/65如果三维曲线是封闭线10月算法在线班50/65GIS中三维建模的实际应用 右上：未使用引导线 左下：输入的引导线 右下：过引导线的曲面10月算法在线班51/65带陷阱的走棋盘 有一个n*m的棋盘网格，机器人最开始在左上角，机器人每一步只能往右或者往下移动。棋盘中有些格子是禁
22、止机器人踏入的，该信息存放在二维数组blocked中，如果blockedij为true，那么机器人不能踏入格子(i,j)。请计算有多少条路径能让机器人从左上角移动到右下角。10月算法在线班52/65状态转移方程 dpij表示从起点到(i,j)的路径条数。只能从左边或者上边进入一个格子 如果(i,j)被占用dpij=0 如果(i,j)不被占用dpij=dpi-1j+dpij1 思考：如果没有占用的格子呢？一共要走m+n2步，其中(m1)步向右，(n-1)步向下。组合数C(m+n2,m-1)=C(m+n-2,n-1)10月算法在线班53/65陷阱走棋盘 在86的矩阵中，每次只能向上或向右移动一格，
23、并且不能经过P。试计算从A移动到B一共有多少种走法。APB10月算法在线班54/65解题过程 从A到B共需要移动12步，其中7步向右，5步向上，可行走法数目为 从A到P共需要8步，其中5步向右，3步向上，可行走法数目为 从P到B共需要4步，其中2步向右，2步向上，可行走法数目为 则，从A到B经过P的路线有56*6=336种；从A到B不经过P的路线有792-336=456种。792512C5658C624C10月算法在线班55/65方格的可行路径数目11111111876543213628211510631642803520104116298707035155145629419612656216
24、110月算法在线班56/65思考题：两次走棋盘 给定m*n的矩阵，每个位置是一个非负的权值，从左上角开始，每次只能朝右和下走，走到右下角；然后，从右下角开始，每次只能朝左和朝上走，走到左上角。求权值总和最大的路径。若相同格子走过两次，则该位置的权值只算一次。10月算法在线班57/65Code10月算法在线班58/65Code split10月算法在线班59/65动态规划总结 动态规划是方法论，是解决一大类问题的通用思路。事实上，很多内容都可以归结为动态规划的思想。KMP中求next数组：已知next0i-1，求nexti；最长回文子串Manacher算法中，已知P0i-1求Pi 何时可以考虑使
25、用动态规划：初始规模下能够方便的得出结论 空串、长度为0的数组、自身等 能够得到问题规模增大导致的变化 递推式状态转移方程10月算法在线班60/65动态规划总结 无后效性 计算Ai时只读取A0i-1，不修改历史 计算Ai时不需要Ai+1n-1的值未来 在实践中往往忽略无后效性：问题本身决定了它是成立的：格子取数问题 通过更改计算次序可以达到该要求：矩阵连乘问题 哪些题目不适合用动态规划？状态转移方程的推导，往往陷入局部而忽略全局。在重视动态规划的同时，别忘了从总体把握问题。10月算法在线班61/65思考题：字符串的交替连接 输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1=“aabcc”，s2=“dbbca”，s3=“aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。换个表述：s1和s2是s3的子序列，且s1s2=s310月算法在线班62/65Code10月算法在线班63/65Code210月算法在线班64/65我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班65/65感谢大家恳请大家批评指正！