leetcode70:爬楼梯

假设你正在爬楼梯。需要 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 阶

解题思路：

假设我们现在站在台阶ii上面。对于我们如何到达的ii，有且仅有两种可能：

1. 我们之前在台阶i-1上面，然后用一步走到了台阶ii上面；

2. 我们之前在台阶i-2上面，然后用两步走到了台阶ii上面。

设函数f(i)f(i)为到达ii的所有可能的方法数量。则有
f(i) = f(i-1) + f(i-2)f(i)=f(i−1)+f(i−2),
即到达ii的方法数等于到达i-1i−1的方法数加上到达i-2i−2的方法数。大的问题depends on小的问题，这就是最基本的动态规划的原则。

作者：what-to-do
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/solution-python3-by-bu-zhi-dao-gan-sha/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。