跳台阶|换硬币

【经典面试必考题】

一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法?(跟顺序有关)

答:状态转移方程:f(n)=f(n-1)+f(n-2)     ---没错,这就是斐波那契数列问题

时间复杂度来讲:

使用递归:O(N2

使用循环:O(N)

拓展一下,如果一次可以跳1级,也可以跳2级,也可以跳5级,求共有多少种跳法?

答:f(n)=f(n-1)+f(n-2)+f(n-5)

 

一共需要n元,如果你有1元和2元纸币。求总共有多少种兑换方法?(跟顺序无关)

答:状态转移方程:f(i+c)+=f(i) 或者f(i)+=f(i-c)      c为面值

代码思路:

用一维数组来解答,初始化一个n+1长度的数组,值为[1,0,0,...,0,0]

两层for循环中使用状态转移方程即可。

for c in coins:

for i in range(n-c+1):

f[i+c]+=f[i]

 

 

2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

跳台阶|换硬币
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close