07-数据解构+算法(第07篇),动态编程!黄袍加身!
引言
在上篇文章《再不会"降维打击"你就Out了!》中,提到了递归算法的两个局限性。本文给出解决方案——动态编程。如果说"递归算法"是圣剑的话,那么"动态编程"就是圣衣。两者加持,你便可以爆发究极小宇宙:)
递归算法局限性详细分析
局限性1(适用性问题):
如果“降维”前的状态集合并不方便用“降维”后的状态集合表示,即状态转移函数不好求,那么该场景使用递归不一定恰当。
下面举个例子来说明:
有两个集合A
和B
,A
中有n
个元素,B中也有n个相同元素,将A中的元素通过映射f,映射到B中的元素,映射f满足:f(f(x))=f(x)
,求这样的不同映射有多少种。
根据在《再不会"降维打击"你就Out了!》中讲到的递归应用的优化套路,很容易看出,规模因子就是n,关键要求的就是状态转移函数g:f(n-1)->f(n)
。
f(n-1)
表示A和B各有n-1
个元素时,不同映射的种数;
f(n)
表示A和B各有n
个元素时,不同映射的种数。
上图左侧表示的就是f(n-1)
对应的一种情况,右侧表示的就是f(n)
对应的一种情况。
在上面图示的情况中:
元素个数等于n-1
时,A中的元素K2映射到B中的元素Kn-1
;
但是元素个数等于n
时,A中的元素K2映射到B中的元素Kn
,此时映射的种数等价于下图映射的种数:
这是一个n-2
个元素到n-1
个元素的映射,显然它的值不一定等于f(n-1)
。
换言之,在本例中,f(n)
并不方便用f(n-1)
来表示,即状态转移函数g:f(n-1)->f(n)
不好求。
原因就是:
问题规模变化时,“形状”变了——从(n-1)->(n-1)变成了(n-2)->(n-1)——直观地说,从“正方形”变成了“梯形”。
如果仍然要用递归来解,那么就需要引入中间态辅助函数,计算“梯形”的函数值。
局限性2(重复计算问题):
在直接递归的过程中部分函数值会被重复计算
为了避免重复计算,一个直接而朴素的想法就是:引入中间态辅助函数,将算过的函数值存下来,递归时再次遇到该函数时,直接从保存结果中取出来。
从上面对两个局限性的分析可以看出:优化递归的方法就是引入中间态辅助函数,保存中间态结果。
这种方法就叫做“动态编程”。
自顶向下 vs. 自底向上
很明显,保存中间态结果,有两种方式——自顶向下或者自底向上。
还是拿《再不会"降维打击"你就Out了!》中的爬台阶的例子来讲。
最终的状态转移函数表达式如下:
当n>=4时:
f(n)=f(n-1)+f(n-2)+f(n-3)
当1<=n<4
时:f(n)=n
当n<1时:f(n)=0
递归的自然方向就是自顶向下。递归的同时,首先查一下保存函数值的线性表,如果查得到,那么就直接“拿来主义”;
如果查不到,那么计算完了函数值之后,也往线性表里保存结果,这样后面的递归步骤如果用得上的话,就节省计算时间了。
这里的线性表是不是有点像“备忘录”呢?所以这个方法也称作“备忘录法”
下面再来看看自底向上。我们逆着递归自然展开的方向,根据状态转移函数,一边查表一边从底部向上逐步计算函数值,并将新计算出来的值也保存到线性表中,供更高层的函数值计算时使用。这种方法就叫做“动态规划”。
由于“动态规划”是逆着递归自然展开的方向,所以写出开的程序结构不再是递归形式,而是递归展开的反向形式——循环结构。
进一步优化
细心的同学肯定发现了:无论是“备忘录法”还是“动态规划”,都要保存所有的中间结果,根据在《空间复杂度你真的懂了吗?》中学到的知识,这必将导致空间复杂度极大。
那么如何优化呢?
还是拿上面的爬台阶的例子来说明。根据上面的树状图示,显然每次求当前层的函数值时,只会用到紧邻的下一层的几个函数值,这意味着更深层的函数值都没有用了,可以舍去、释放内存。
换言之,无论是使用“备忘录法”还是“动态规划”,都要分析状态转移函数,看看“降维”前后到底涉及哪些状态,不在这个状态集合里的函数值都可以舍去、释放内存。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com