做网站赔了8万,深圳做网站哪家便宜,集团网站建设多少钱,做个店铺小程序多少钱作者简介#xff1a;大家好#xff0c;我是smart哥#xff0c;前中兴通讯、美团架构师#xff0c;现某互联网公司CTO 联系qq#xff1a;184480602#xff0c;加我进群#xff0c;大家一起学习#xff0c;一起进步#xff0c;一起对抗互联网寒冬 学习必须往深处挖… 作者简介大家好我是smart哥前中兴通讯、美团架构师现某互联网公司CTO 联系qq184480602加我进群大家一起学习一起进步一起对抗互联网寒冬 学习必须往深处挖挖的越深基础越扎实
阶段1、深入多线程阶段2、深入多线程设计模式阶段3、深入juc源码解析
阶段4、深入jdk其余源码解析
阶段5、深入jvm源码解析
码哥源码部分
码哥讲源码-原理源码篇【2024年最新大厂关于线程池使用的场景题】
码哥讲源码【炸雷啦炸雷啦黄光头他终于跑路啦】
码哥讲源码-【jvm课程前置知识及c/c调试环境搭建】
码哥讲源码-原理源码篇【揭秘join方法的唤醒本质上决定于jvm的底层析构函数】
码哥源码-原理源码篇【Doug Lea为什么要将成员变量赋值给局部变量后再操作】
码哥讲源码【你水不是你的错,但是你胡说八道就是你不对了】
码哥讲源码【谁再说Spring不支持多线程事务你给我抽他】
终结B站没人能讲清楚红黑树的历史不服等你来踢馆
打脸系列【020-3小时讲解MESI协议和volatile之间的关系那些将x86下的验证结果当作最终结果的水货们请闭嘴】
引言
在上篇文章《再不会降维打击你就Out了!》中提到了递归算法的两个局限性。本文给出解决方案——动态编程。如果说递归算法是圣剑的话那么动态编程就是圣衣。两者加持你便可以爆发究极小宇宙 递归算法局限性详细分析
局限性1适用性问题
如果“降维”前的状态集合并不方便用“降维”后的状态集合表示即状态转移函数不好求那么该场景使用递归不一定恰当。
下面举个例子来说明
有两个集合A和BA中有n个元素B中也有n个相同元素将A中的元素通过映射f映射到B中的元素映射f满足f(f(x))f(x)求这样的不同映射有多少种。
根据在《再不会降维打击你就Out了!》中讲到的递归应用的优化套路很容易看出规模因子就是n关键要求的就是状态转移函数gf(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)来表示即状态转移函数gf(n-1)-f(n)不好求。
原因就是
问题规模变化时“形状”变了——从(n-1)-(n-1)变成了(n-2)-(n-1)——直观地说从“正方形”变成了“梯形”。
如果仍然要用递归来解那么就需要引入中间态辅助函数计算“梯形”的函数值。
局限性2重复计算问题
在直接递归的过程中部分函数值会被重复计算
为了避免重复计算一个直接而朴素的想法就是引入中间态辅助函数将算过的函数值存下来递归时再次遇到该函数时直接从保存结果中取出来。
从上面对两个局限性的分析可以看出优化递归的方法就是引入中间态辅助函数保存中间态结果。
这种方法就叫做“动态编程”。 自顶向下 vs. 自底向上
很明显保存中间态结果有两种方式——自顶向下或者自底向上。
还是拿《再不会降维打击你就Out了!》中的爬台阶的例子来讲。
最终的状态转移函数表达式如下
当n4时
f(n)f(n-1)f(n-2)f(n-3
当1n4时f(n)n
当n1时f(n)0
递归的自然方向就是自顶向下。递归的同时首先查一下保存函数值的线性表如果查得到那么就直接“拿来主义”
如果查不到那么计算完了函数值之后也往线性表里保存结果这样后面的递归步骤如果用得上的话就节省计算时间了。
这里的线性表是不是有点像“备忘录”呢所以这个方法也称作“备忘录法” 下面再来看看自底向上。我们逆着递归自然展开的方向根据状态转移函数一边查表一边从底部向上逐步计算函数值并将新计算出来的值也保存到线性表中供更高层的函数值计算时使用。这种方法就叫做“动态规划”。
由于“动态规划”是逆着递归自然展开的方向所以写出开的程序结构不再是递归形式而是递归展开的反向形式——循环结构。 进一步优化
细心的同学肯定发现了无论是“备忘录法”还是“动态规划”都要保存所有的中间结果这必将导致空间复杂度极大。
那么如何优化呢
还是拿上面的爬台阶的例子来说明。根据上面的树状图示显然每次求当前层的函数值时只会用到紧邻的下一层的几个函数值这意味着更深层的函数值都没有用了可以舍去、释放内存。
换言之无论是使用“备忘录法”还是“动态规划”都要分析状态转移函数看看“降维”前后到底涉及哪些状态不在这个状态集合里的函数值都可以舍去、释放内存。
