源代码管理网站,物流网站建设可行性分析,免费做网站的优缺点,吃什么补肾效果最好上一篇:算法随笔_39: 最多能完成排序的块_方法2-CSDN博客 题目描述如下:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a;n 2
输出#xff1a;2
解释
题目描述如下:
假设你正在爬楼梯。需要 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) 。
因此当n2时走n阶楼梯总共的方法数m(n) m(n-1) m(n-2) 。
这是一道典型的动态规划题型。从这个公式我们可以看出求n阶楼梯的方法数仅仅取决于n-1n-2阶楼梯的方法数。因此我们在代码实现的时候只需要维护两个变量n_1n_2来不断的计算出m(n) 。
由于我们已知m(1) 1m(2) 2我们可以写出如下的代码:
class Solution(object):def climbStairs(self, n)::type n: int:rtype: intif n1:return 1if n2:return 2n_12n_21res0for i in range(3,n1):if i3:n_2n_1n_1resresn_1n_2return res
