70. 爬楼梯
假设你正在爬楼梯。需要 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 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
对于这样一个问题，我们先来思考下能否递归的解决，它内部是否有递归的结构。
我们自顶向下的思考问题，直接考虑第nnn阶台阶，并且假设它下面的n−1n-1n−1阶,n−2n-2n−2阶等子问题都已经解决了。
如果我们要想爬上nnn阶台阶，因为一次要么爬111阶，要么爬222阶，所以爬nnn阶台阶有两种可能。
从n−1n-1n−1阶再爬111阶或者从n−2n-2n−2阶再爬222阶。
不难看出这是一个递归问题，我们把问题转换为爬n−1n-1n−1阶有多少种方法和爬n−2n-2n−2阶有多少种方法。然后把这两个问题的答案相加就好了。这样把一个大的问题转换为两个小问题。
博客专家
原创文章 163获赞 247访问量 17万+
关注
私信
展开阅读全文
作者：愤怒的可乐
