爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        steps = [1, 2]
        if n == 1 or n == 2:
            return n
        for i in xrange(2, n):
            sn = steps[i-1] + steps[i-2]
            steps.append(sn)
        return steps[-1]

思路:仔细分析就可以得出当前的台阶数是上一阶台阶数和上上阶台阶数之和,因为当前台阶只有可能从上一层或者上上层到达,所以求出上一层或者上上层的台阶数就可以了,依此类推,就是一个叠加的过程。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶...
    小白学编程阅读 303评论 0 0
  • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶...
    ZMT_sherry阅读 191评论 0 0
  • 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶...
    kayleeWei阅读 617评论 0 1
  • Q: 前段时间笔试,遇到了以前学的一个算法,大学时没认真想,只是记着怎么写,现在得空,总结一下这个问题的解法。题目...
    我叫没名字啊阅读 12,902评论 5 15
  • 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶...
    尼小摩阅读 799评论 0 0