递归思维:计算爬楼梯歩法

问题描述:

爬楼梯,可以一步一梯,也可以一步两梯,问:走N级台阶有多少种步法?

问题算法:

设走上n级台阶有f(n)种方法,将这n种方法拆分为两大类:

1、最后一次走了一级台阶,那么此前有f(n-1)种步法;

2、最后一次走了二级台阶,那么此前有f(n-2)种步法;

3、得出递推公式:f(n)=f(n-1)+f(n-2);

4、显而易见,f(1)=1,f(2)=2。

Python代码如下:

def climbStairs(n):

if n==1:

return 1

elif n==2:

return 2

else:

return(climbStairs(n-1)+climbStairs(n-2))

n=int(input("请输入要走的台阶数n:"))

print(climbStairs(n))

学习心得:

关键点在于从最后一步往前推,让人顿时豁然开朗。虽然递归算法的代码效率不高,但好处在于思路非常的简单清晰。感觉递归的思考方式非常给力,平时生活学习中是否有类似应用场景呢?

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171223G0NDWN00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券