您当前位置：首页 > php开源 > php教程 > Climbing Stairs -- leetcode

Climbing Stairs -- leetcode

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

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; } };

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

------分隔线----------------------------

上一篇 部署Lync Server 2013时系统提示Prerequisite installation failed安装必备组件失败SqlInstanceRtcLoc

下一篇 [置顶] 数据库调优教程（十）【精华章节】解决like ’%str’ 时索引不被使用的4种方法

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点