简单暴力到dp的优化(萌新篇)

兔老大 发表于 2021/04/22 01:40:27 2021/04/22
【摘要】 想写一系列文章,总结一些题目,看看解决问题、优化方法的过程到底是什么样子的。   系列问题一:斐波那契数列问题 在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)根据定义,前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55 问题一: 给定一个正...

想写一系列文章,总结一些题目,看看解决问题、优化方法的过程到底是什么样子的。

 

系列问题一:斐波那契数列问题

在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)根据定义,前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

问题一:

给定一个正整数n,求出斐波那契数列第n项(这时n较小)

解法一:最笨,效率最低,暴力递归,完全是抄定义。请看代码


  
  1. def f0(n):
  2. if n==1 or n==2:
  3. return 1
  4. return f(n-1)+f(n-2)

 

分析一下,为什么说递归效率很低呢?咱们来试着运行一下就知道了

 

比如想求f(10),计算机里怎么运行的?

 

每次要计算的函数量都是指数型增长,时间复杂度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是,进行了大量重复计算,比如图中的f(8),f(7).....等等,你会发现f(8)其实早就算过了,但是你后来又要算一遍。

如果我们把计算的结果全都保存下来,按照一定的顺序推出n项,就可以提升效率, 斐波那契(所有的一维)的顺序已经很明显了,就是依次往下求。。

优化1


  
  1. def f1(n):
  2. if n==1 or n==2:
  3. return 1
  4. l=[0]*n
  5. l[0],l[1]=1,1
  6. for i in range(2,n):
  7. l[i]=l[i-1]+l[i-2]
  8. return l[-1]

 

时间复杂度o(n),依次往下打表就行,空间o(n).

继续优化:既然只求第n项,而斐波那契又严格依赖前两项,那我们何必记录那么多值呢?记录前两项就行了

 

优化2


  
  1. def f2(n):
  2. a,b=1,1
  3. for i in range(n-1):
  4. a,b=b,a+b
  5. return a

此次优化做到了时间o(n),空间o(1)

附:这道题掌握到这里就可以了,但是其实有时间o(log2n)的方法

 

优化三:

学习过线性代数的同学们能够理解:

 

结合快速幂算法,我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)

注意:只有递归式不变,才可以用矩阵+快速幂的方法。

注:优化三可能只有在面试上或竞赛中用,当然,快速幂还是要掌握的。

 

经过这个最简单的斐波那契,大家有没有一点感觉了?

好,我们继续往下走

(补充:pat、蓝桥杯原题,让求到一万多位,结果模一个数。

可以每个结果都对这个数取模,否则爆内存,另:对于有多组输入并且所求结果类似的题,可以先求出所有结果存起来,然后直接接受每一个元素,在表中查找相应答案)

 

问题二:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

依旧是找递推关系,分析:跳一阶,就一种方法,跳两阶,它可以一次跳两个,也可以一个一个跳,所以有两种,三个及三个以上,假设为n阶,青蛙可以是跳一阶来到这里,或者跳两阶来到这里,只有这两种方法。它跳一阶来到这里,说明它上一次跳到n-1阶,同理,它也可以从n-2跳过来,f(n)为跳到n的方法数,所以,f(n)=f(n-1)+f(n-2)

和上题的优化二类似。

因为递推式没变过,所以可以用优化三

 

问题三:

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?提示,大矩形看做是长度吧

请读者自己先思考一下吧。。。仔细看题。。仔细思考

如果n是1,只有一种,竖着放呗;n是2,两种:

n等于3,三种:

 

题意应该理解了吧?

读到这里,你们应该能很快想到,依旧是斐波那契式递归啊。

对于n>=3:怎么能覆盖到三?只有两种办法,从n-1的地方竖着放了一块,或者从n-2的位置横着放了两块呗。

和问题二的代码都不用变。

 

问题四:

给定一个由0-9组成的字符串,1可以转化成A,2可以转化成B。依此类推。。25可以转化成Y,26可以转化成z,给一个字符串,返回能转化的字母串的有几种?

比如:123,可以转化成

1 2 3变成ABC,

12 3变成LC,

1 23变成AW,三种,返回三,

99999,就一种:iiiii,返回一。

分析:求i位置及之前字符能转化多少种。

两种转化方法,一,字符i自己转换成自己对应的字母,二,和前面那个数组成两位数,然后转换成对应的字母

假设遍历到i位置,判断i-1位置和i位置组成的两位数是否大于26,大于就没有第二种方法,f(i)=f(i-1),想反,等于f(i-1)+f(i-2)

注意:递归式不确定,不能用矩阵快速幂

 

(这几个题放到这里就是为了锻炼找递归关系的能力,不要只会那个烂大街的斐波那契)

 


  
  1. '''
  2. 斐波那契问题:
  3. 斐波纳契数列以如下被以递归的方法定义:
  4. F(1)=1
  5. F(2)=1
  6. F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
  7. '''
  8. #暴力抄定义,过多重复计算
  9. def f0(n):
  10. if n==1 or n==2:
  11. return 1
  12. return f(n-1)+f(n-2)
  13. #记录结果后依次递推的优化,时间O(N)
  14. def f1(n):
  15. if n==1 or n==2:
  16. return 1
  17. l=[0]*n
  18. l[0],l[1]=1,1
  19. for i in range(2,n):
  20. l[i]=l[i-1]+l[i-2]
  21. return l[-1]
  22. #既然严格依赖前两项,不必记录每一个结果,优化空间到O(1)
  23. def f2(n):
  24. a,b=1,1
  25. for i in range(n-1):
  26. a,b=b,a+b
  27. return a

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/79912328

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。