国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > Climbing Stairs -- leetcode

Climbing Stairs -- leetcode

来源:程序员人生   发布时间:2015-04-20 07:55:39 阅读次数:2957次

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?


此题用动太计划解决。

递归式为:dp[n] = dp[n⑴] + dp[n⑵]

爬到第n层,有两种途径,1步从n⑴上来,1下跨两步从n⑵上来。

即要求出爬到第n层的所以方法,需知道爬到第n⑴层,n⑵层的方法。


关于出发点0层,可以定义为有1种方法,即不动。既不跨1步,也不跨两步,就到达。

比0层更低的,定义为0种办法。

这也可看做是Fibonacci求解。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...


class Solution { public: int climbStairs(int n) { if (n == 0 || n == 1) return 1; int stepOne = 1, stepTwo = 1; int allWays; for (int i=2; i<=n; i++) { allWays = stepOne + stepTwo; stepTwo = stepOne; stepOne = allWays; } return allWays; } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生