淄博晨曦网站建设,深圳网站建设定制开发服务,网页视频怎么下载保存,惠州网站建设创业【摘要】为了提高算法的效率#xff0c;动态规划是在算法实践中经常使用的一个思想#xff0c;有些问题会非常适合使用动态规划的思想来设计算法。本文将借助LeetCode上的一些例子#xff0c;来讲解和说明动态规划在算法案例中的一些实践。
【关键词】 动态规划 LeetCode 算…【摘要】为了提高算法的效率动态规划是在算法实践中经常使用的一个思想有些问题会非常适合使用动态规划的思想来设计算法。本文将借助LeetCode上的一些例子来讲解和说明动态规划在算法案例中的一些实践。
【关键词】 动态规划 LeetCode 算法效率 算法
一、引言
生活中会遇到很多的问题在使用代码来进行抽象逻辑的时候有时候会需要抽象成数学上的算法来提高处理的效率。因为计算机的资源是有限的并不能简单地、暴力地帮我们处理所有的问题。而且很多重复的工作也有必要通过抽象成算法来简化。比如举一个常见的例子从1~n累加的和就可以通过高斯算法来表示得到(1n)*n/2这样的结果这样可以大大简化运算的步骤从而提高算法的效率。同样的例子还有很多。算法可以有效的帮助到我们。
常用的有几大算法分别是分治法、贪婪算法、动态规划、穷举法。当然还有一些分支定界法、回朔法、哈希表、深度优先搜索等等在这里不做主要的介绍在这里主要介绍的是动态规划以及和动态规划思想有关算法的一些区别和需要注意的地方。
二、何为动态规划
动态规划英文名称是dynamic programming这里的programing不是指程序代码而是一种方法一种算法思想是解决某一类算法的思想通过组合子问题的解来求解最优解的方法。广泛应用在计算机科学、数学、生物信息学还有管理学科和经济学当中通过把复杂的问题拆解成相对简单一些的子问题来求解。这样通过分解成子问题再通过子问题的最优集合我们就可以方便的解决原来可能很复杂的问题。
关于子问题有两个概念是需要了解的第一个是最优子结构动态规划要解决的就是从一堆问题的解决方案中寻找问题的最优解当然这种最优解可能不存在也可能用动态规划是无法寻找和找不到的。当找到最优解之后通过把最优解拼装起来就可以得到最后的解了。
如果问题比较复杂的话那么非常有可能不止只有一个最优解甚至最优解也可以是一堆最优解的结合这就是第二个关于子问题需要了解的就是重复子问题。遇到这种情况一般就需要通用递归重复子问题来得到最终的结果当重复的子问题很多的时候动态规划可以帮助我们减少很多重复的计算量。但是如果在使用递归方法来解决算法问题时没有出现可以重复的子问题那么就没必要非要使用动态规划的思想来解决一般的递归方法也是可以很好地胜任的。
还有一个关于子问题的概念是无后效性也就是说每个子问题可以是相互独立的在推导的过程中后面的结果不该再去对这个子问题的结果产生影响。这一点也很重要因为动态规划一般都是自顶向下来进行的如果是子问题之间相互关联性很大的话那就说明这并不需要来通过动态规划来处理也会严重影响到最后的算法的效率问题或者这个算法有可能无法在有限的时间内终止这都是不符合我们预期的。
我们可以这样说寻找一个问题的子问题并且完善子问题之间的关系的写出状态转移方程就是动态规划思想的基本思想过程了。也基本上可以说如果能够证明该问题存在最优的子问题并且能够通过子问题的不断重复递归来得到最终的最优解那么就说明该问题适合使用动态规划来解答。
以下通过几个案例来详细解答这个过程。
三、案例一不含连续1的非负整数
先来一道关于数位动态规划的案例 给定一个正整数n找出小于或等于n的非负整数中其二进制表示不包含连续的1的个数。1 方法1. 最简单粗暴的方法
首先我们用最简单粗暴的方法来计算一下这个案例代码如下
class Solution {public int findIntegers(int n) {int result n 1;for (int i n; i 0; i--) {int nextNumber i;int remainder nextNumber % 2;while (nextNumber ! 0) {int lastRemainder remainder;nextNumber nextNumber / 2;remainder nextNumber % 2;if (lastRemainder 1 remainder 1) {result--;break;}}}return result;}
}以上方法当输入是2147483647时得到的结果是3524578计算耗时为30063ms。 十进制转二进制的方法就是除二取余法以上方法从0~n每个数都计算一遍只要有出现连续的1就在总数上减一这样就可以得到最终的结果。
方法2. 使用动态规划的思想来解析
上面的方法最后的耗时显然是一个非常长的时间那么我们该如何使用动态规划来分析这道题呢按照暴力计算的思路就是把全部的数都计算一遍但显然没有这个必要去全部都去计算一遍。 举个例子比如数字77转成二进制的数是111 转成二进制表示的话 0 : 0001 : 0012 : 0103 : 0114 : 1005 : 1016 : 1107 : 111
以上符合条件的数分别是0110100101一共5个数。我们可以把上面的数使用二叉字典树的形式表达出来如下图。 #mermaid-svg-La0S4Ss5O6sJ6RQR {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .error-icon{fill:#552222;}#mermaid-svg-La0S4Ss5O6sJ6RQR .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-La0S4Ss5O6sJ6RQR .marker{fill:#333333;stroke:#333333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .marker.cross{stroke:#333333;}#mermaid-svg-La0S4Ss5O6sJ6RQR svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .cluster-label text{fill:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .cluster-label span{color:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .label text,#mermaid-svg-La0S4Ss5O6sJ6RQR span{fill:#333;color:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .node rect,#mermaid-svg-La0S4Ss5O6sJ6RQR .node circle,#mermaid-svg-La0S4Ss5O6sJ6RQR .node ellipse,#mermaid-svg-La0S4Ss5O6sJ6RQR .node polygon,#mermaid-svg-La0S4Ss5O6sJ6RQR .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .node .label{text-align:center;}#mermaid-svg-La0S4Ss5O6sJ6RQR .node.clickable{cursor:pointer;}#mermaid-svg-La0S4Ss5O6sJ6RQR .arrowheadPath{fill:#333333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-La0S4Ss5O6sJ6RQR .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-La0S4Ss5O6sJ6RQR .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-La0S4Ss5O6sJ6RQR .cluster text{fill:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR .cluster span{color:#333;}#mermaid-svg-La0S4Ss5O6sJ6RQR div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-La0S4Ss5O6sJ6RQR :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 0 1 0 1 0 1 0 _ 110 0 1 0 1 0 1 可以发现里面是会有很多重复计算的当数字小的时候这点儿耗时可以忽略但是当数字很大的时候这种计算就会是非常耗时的有着更多无意义的重复计算。 先观察可以发现当右子树连续出现两个1的时候代表着后面的数全部都是不符合要求的。
也就是说我们要计算的二进制表示中不含连续的1的数量可以描述成要计算根节点为0的满二叉树中不含连续的1的路径数量。通过计算我们可以列出来已知的一些结果。可以发现要计算的根节点为0的满二叉树中不含连续1的路径数量可以发现是上面2层不含连续1的路径数量之和。结果如下
f(2^0)1f(2^1)1f(2^2)2f(2^3)3f(2^3)5
我们依据斐波那契数列的关系可以得出状态转移方程 f ( 2 n ) { f ( 2 n − 1 ) f ( 2 n − 2 ) n ≥ 2 1 n 2 f(2^n) \begin{cases} f(2^{n-1})f(2^{n-2}) \text{n}\geq{2}\ 1 \text{n}{2} \end{cases} f(2n){f(2n−1)f(2n−2)n≥2 1n2
最后的代码如下
class Solution {public int findIntegers(int n) {ListInteger data new ArrayList();//添加斐波那契数列的初始值data.add(1);data.add(1);//利用斐波那契数列计算出最大数的有效结果for (int i 2; i n; i) {int val 1 i;if (val 0 val n) {data.add(data.get(data.size() - 1) data.get(data.size() - 2));} else {data.add(data.get(data.size() - 1) data.get(data.size() - 2));break;}}boolean haveOne false;int result 0;for (int i data.size() - 1; i 0; --i) {// 位移用来表示在二进制上1向左移动了几位比如 1 2 的结果是100也就是十进制的4int val 1 i;// 位与二进制数上只有当都是1时才为1用来筛选出最高位的1所在的位置if ((n val) ! 0) {//把已经出现的左边树的数都加上result data.get(i 1);//如果出现连续的1这里跳出循环代表的下面的数都不会再符合条件if (haveOne) {break;}haveOne true;} else {haveOne false;}if (i 0) {//如果计算到了这里需要再加1因为0也是需要被计入符合条件的数字的result;}}return result;}
}输出的结果在同一台电脑同样的配置下当输入是2147483647时得到的结果是3524578计算耗时为20ms。可以看到相比较直接的暴力计算最终的性能有了非常大的提升。
四、案例二不同的二叉搜索树
这是一道关于计数问题的动态规划的案例 给你一个整数n求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种返回满足题意的二叉搜索树的种数。2 1. 什么是二叉搜索树
所谓的二叉搜索树就是节点的左子树所有的值一定小于该节点右子树所有的值一定大于该节点。比如n5时可以得到 #mermaid-svg-KxcA5NCkmAqzf8fy {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .error-icon{fill:#552222;}#mermaid-svg-KxcA5NCkmAqzf8fy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-KxcA5NCkmAqzf8fy .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-KxcA5NCkmAqzf8fy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-KxcA5NCkmAqzf8fy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-KxcA5NCkmAqzf8fy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-KxcA5NCkmAqzf8fy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-KxcA5NCkmAqzf8fy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-KxcA5NCkmAqzf8fy .marker.cross{stroke:#333333;}#mermaid-svg-KxcA5NCkmAqzf8fy svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-KxcA5NCkmAqzf8fy .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .cluster-label text{fill:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .cluster-label span{color:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .label text,#mermaid-svg-KxcA5NCkmAqzf8fy span{fill:#333;color:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .node rect,#mermaid-svg-KxcA5NCkmAqzf8fy .node circle,#mermaid-svg-KxcA5NCkmAqzf8fy .node ellipse,#mermaid-svg-KxcA5NCkmAqzf8fy .node polygon,#mermaid-svg-KxcA5NCkmAqzf8fy .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-KxcA5NCkmAqzf8fy .node .label{text-align:center;}#mermaid-svg-KxcA5NCkmAqzf8fy .node.clickable{cursor:pointer;}#mermaid-svg-KxcA5NCkmAqzf8fy .arrowheadPath{fill:#333333;}#mermaid-svg-KxcA5NCkmAqzf8fy .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-KxcA5NCkmAqzf8fy .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-KxcA5NCkmAqzf8fy .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-KxcA5NCkmAqzf8fy .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-KxcA5NCkmAqzf8fy .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-KxcA5NCkmAqzf8fy .cluster text{fill:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy .cluster span{color:#333;}#mermaid-svg-KxcA5NCkmAqzf8fy div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-KxcA5NCkmAqzf8fy :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 1 3 2 1 2 3 1 2 3 3 2 1 3 1 2 2.方法一 使用动态规划的思想来解析
要构建一颗二叉搜索树我们可以把题目这样描述给定一个有序的序列1~n遍历这个序列对于每个数字i来说把 i i i当做根节点把1(i-1)当做左子树把(i1)n当做右子树接着递归遍历这两个序列重复前面的操作最后计数就可以得到我们要的结果。因为一开始遍历的时候根的值不一样我们可以认为通过这种方式构建出来的二叉搜索树都是唯一的。
接下来我们定义两个函数 G ( n ) G(n) G(n): 把题目要求的有序的序列1~n构建起来的不同二叉树搜索树的计数个数也就是我们最终想要得到的结果这里和输入的序列的内容无关只要是序列里面的数都不同就可以了n表示数量。 F ( i , n ) F(i,n) F(i,n):以i为树的根把1(i-1)当做左子树把(i1)n当做右子树构建起来的不同二叉树的计数个数n表示数量i表示根节点。
根据上面的描述我们可以得到如下的公式 G ( n ) ∑ i 1 n F ( i , n ) (1) G(n)\sum_{i1}^{n}{F(i,n)} \tag{1} G(n)i1∑nF(i,n)(1)
首先我们定义当n1或者n2时 G ( n ) 1 , G ( n ) 2 G(n)1, G(n)2 G(n)1,G(n)2。
接着我们来计算 F ( i , n ) F(i,n) F(i,n)以i为树的根计算的所有的二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积再加上根节点之后就构建成一颗二叉搜索树了。所谓的笛卡尔积就是在集合论中两个集合中所有可能的有序对的集合。举例说明一个序列[1,2,3,4,5,6]以i3左边的序列[1,2]右边的序列[4,5,6]。左边的序列构建起来的二叉树搜索树的数量是 G ( 2 ) G(2) G(2)右边的序列构建起来的二叉搜索树的数量是 G ( 3 ) G(3) G(3)。这样我们就可以得到 F ( 3 ) G ( 2 ) ⋅ G ( 3 ) F(3)G(2) \cdot G(3) F(3)G(2)⋅G(3)。也就是说我们会发现因为 G ( n ) G(n) G(n)其实和输入序列内容无关只和输入的不同序列的数量有关系。所以我们得到如下公式 F ( i , n ) G ( i − 1 ) ⋅ G ( n − i ) (2) F(i,n)G(i-1) \cdot G(n-i) \tag{2} F(i,n)G(i−1)⋅G(n−i)(2) 将上面的公式(1)和公式(2)合并一下就可以得到我们想要的最终结果 G ( n ) ∑ i 1 n G ( i − 1 ) ⋅ G ( n − i ) (3) G(n)\sum_{i1}^{n}G(i-1) \cdot G(n-i) \tag{3} G(n)i1∑nG(i−1)⋅G(n−i)(3) 据此我可以写下如下的代码
class Solution {public long numTrees(int n) {long[] tree new long[n 1];tree[0] 1;tree[1] 1;for (int i 2; i n; i) {for (int j 1; j i; j) {tree[i] tree[j - 1] * tree[i - j];}}return tree[n];}
}当输入是35时得到的结果是3116285494907301262计算耗时为21ms。 以上就是我们的分析过程。
2.方法二数学公式
从上面的推导我们就可以发现我们可以发现这是个数学上的公式在数学上我们上面推导出来的 G ( n ) G(n) G(n)这个函数被称为卡塔兰数。具体的公式是 C 0 1 , C n 1 2 ( 2 n 1 ) n 2 C n C_01,C_{n1}\frac{2(2n1)}{n2}C_n C01,Cn1n22(2n1)Cn
这是一个在组合数学上非常出名的公式。其实这个公式和上面的动态规划思想是一样的只是直观地给出来最终的结果这里就不对卡塔兰数进行证明了。我们会发现这个答案的解的结果是呈爆炸增长的。
五、动态规划与其他算法思想之间的关系
1. 分治策略
分治的思想是把一个问题分解成一系列的小问题把问题的规模缩小到可以解决的程度然后通过解决这些小问题再合并之后得到最终的结果。听上去和动态规划的想法是一样的。但其实是不一样的动态规划是无数个无数个子问题的重复是存在重复的子问题的。但是分治思想是把问题拆解之后变成一个个独立的小问题并且和原问题描述是一致的只是规模缩小了很多再然后对计算结果进行合并比如归并排序就是把一堆的数组平均的分成两半然后在这两半里面进行排序这就是典型的分治思想。还比如快速排序把数组随机的分成两半然后不断地递归处理这些数组来得到最终的结果注意这里分成的这两半数是不一样的而且还存在不断的递归前面的子问题会影响到后面的子问题的情况。所以说有没有重复子问题的出现就是动态规划和分治最重要的差别。
如果一个问题可以通过拆解成独立的子问题然后再把一堆的独立子问题再合并到一起那么一般情况下就可以考虑使用分治策略。但是如果这种拆解之后的子问题中包含很多公共子问题的话那么使用分治的效率就会低很多因为这个时候会有很多的重复的公共来浪费算法的性能这种时候使用动态规划来解决也许是个不错的选择。
2. 贪心算法
贪心算法是比较于分治和动态规划简单一些的方法说简单并不是说这种方法实现起来不难而是说相比较于分治和动态规划它的复杂度很低也相对容易理解。而且分治和动态规划是要穷举并覆盖原问题所有的情况的但是贪心算法是可以不用覆盖到所有的情况只要能得出最优的结果就可以结束了。贪心算法不要求存在最优的结果而首先考虑的是局部最优通过一系列的局部最优在有些情况下就会得到全局最优即便不是全局最优的也一般不会是最差的结果如果是可以通过求解局部最优就能得到全局最优的话那一定是可以使用贪心算法的。
贪心算法的基本思路一般是首先把原来的问题分解成若干个子问题然后求解这些子问题之后把这些子问题组合起来就得到最终的结果了。也同样的贪心算法也要求子问题是符合无后效性的就是说后面阶段的求解不会再去影响到前面结果的值保证子问题的独立性。
举个例子比如柠檬水找零找零问题3一个柠檬水摊上一杯水5美元一次购买一杯按顺序找零顾客支付的面额只有5美元10美元20美元按顺序支付当场点清。初始时你没有一分钱给你一串付款数字判断是否能够最终找零。
这个问题就可以这样子来分析拆解。首先如果给的是5美元那可以直接收下你的账户上5美元数量加一。然后如果给的是10美元那你只能找零5美元然后你的户头上10美元的数量加一5美元的数量减一。再然后如果给的是20美元有两种支付方式一种是给一张10美元和一张5美元一种是给三张5美元的这样20美元的数量就加一但是20美元并不能用于之后的支付可以忽略那就只需要统计10美元和5美元的数量即可在这里你需要尽可能使用第一种支付方式来支付这样你手上的5美元数量会不断增加。
整个过程后面的的顾客支付的数字不会影响到前面的数字只要依据这三种情况来分段支付即可直到手上美元数量无法再进行后续的支付。这个过程就是使用到了贪心算法而之所以使用到贪心算法是因为面值的的大小固定在5美元10美元20美元这三种上面并且是按照顺序来支付的所以按照贪心算法的思想并不需要去求解所有的情况只需要当前的数字是否能够满足条件位置直到需要求解的结果出来即可也就是说局部的最优解就是全局的最优解这符合我们的预期。
分治策略、贪心算法和动态规划都和拆解子问题有关区别只是关于子问题有着不一样的要求根据不同的分析来解决实际中遇到的困难。分治和动态规划都要求对最后得到的子问题全部解出来但是贪心算法不需要只要解到结果就可以了。贪心算法和动态规划都要求设计的子问题是满足最优结构的但是分治策略可以不是最优的子问题。
六、总结
本文主要通过两个案例来详细说明了动态规划是如何进行和思考的。案例一是针对数位相关的动态规划的问题。在案例一中我们会发现使用动态规划的方法与单纯的使用暴力穷举法相比性能有着非常大的提升。但这并不是说穷举法就没有效了。使用动态规划也是要穷举所有的子问题来处理的但是当我们找不到合适的算法来解决问题时使用简单暴力的穷举法也可以成为我们的选择虽然往往这样的情况下会非常的耗时。
案例二是关于计数相关的动态规划的问题。通过拆解子问题划分成解决左子树和右子树的序列就可以递归的得到最终的结果。当然这是分析的过程。所以说动态规划是一个算法思想是帮助我们理解和分析问题的算法思想就和分治策略和贪心算法是一样的。合理使用算法思想是可以到帮助我们的。
同时在最后要说一下算法的分析方法有非常多的思路不要局限在某个问题上要合理应用合理学习这样才能更快更方便的得到问题的解。
参考文献
[1] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein算法导论[M].殷建平徐云王刚刘晓光苏明邹恒明王宏志. 机械工业出版社2012-12 https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones ↩︎ https://leetcode-cn.com/problems/unique-binary-search-trees/ ↩︎ https://leetcode-cn.com/problems/lemonade-change ↩︎
