算法随笔_40: 爬楼梯

上一篇:算法随笔_39: 最多能完成排序的块_方法2-CSDN博客

=====

题目描述如下:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

=====

算法思路:

为了下面叙述方便，我们设m(i) 表示走i阶楼梯需要的方法数。

根据题目的要求和示例，我们可以发现如下的递推关系:

走第一步，我们有两种选择，1阶或2阶。

如果我们选择走1阶，那么我们还剩n-1阶需要完成。所需的方法数为m(n-1) 。

如果我们选择走2阶，那么我们还剩n-2阶需要完成。所需的方法数为m(n-2) 。

因此，当n>2时，走n阶楼梯总共的方法数m(n) =m(n-1) +m(n-2) 。

这是一道典型的动态规划题型。从这个公式，我们可以看出，求n阶楼梯的方法数仅仅取决于n-1，n-2阶楼梯的方法数。因此我们在代码实现的时候，只需要维护两个变量n_1，n_2来不断的计算出m(n) 。

由于我们已知m(1) =1，m(2) =2，我们可以写出如下的代码:

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n==1:return 1if n==2:return 2n_1=2n_2=1res=0for i in range(3,n+1):if i>3:n_2=n_1n_1=resres=n_1+n_2return res