题目描述
假设你正在爬楼梯。需要 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 阶
提示：
1 <= n <= 45
C语言版
/*70_爬楼梯*/ /*动态规划 f(n)=f(n-1)+f(n-2)*/ int climbStairs(int n) { int i = 0; int ret[46]; ret[0] = 1; ret[1] = 1; if (n > 1) { for (i = 2; i <= n; i++) { ret[i] = ret[i - 1] + ret[i - 2]; } } return ret[n]; } /*优化 因为在递推公式中，我们只需要f(n-1),f(n-2)来退出n对应的总类，n-2之前的数据无需保留 所以只用三个数来记录状态即可(滚动)，不需用数组来记录所有值 */ int climbStairs(int n) { int i = 0; int num1 = 0, num2 = 0, num3 = 1; for (i = 0; i < n; i++) { num1 = num2; num2 = num3; num3 = num1 + num2; } return num3; }
C++版
//70_爬楼梯 class Solution { public: int climbStairs(int n) { vector<int> ret; ret.push_back(1); ret.push_back(1); if (n > 1) { for (int i = 2; i <= n; i++) { ret.push_back(ret[i - 1] + ret[i - 2]); } } return ret[n]; } }; //优化 class Solution { public: int climbStairs(int n) { int num1 = 0, num2 = 0, num3 = 1; for (int i = 0; i < n; i++) { num1 = num2; num2 = num3; num3 = num1 + num2; } return num3; } };
Python版
class Solution: def climbStairs(self, n: int) -> int: f = list() f.append(1) f.append(1) if n < 2: return f[n] for i in range(2, n + 1): f.append(f[i - 1] + f[i - 2]) return f[n] #优化空间复杂度 class Solution: def climbStairs(self, n: int) -> int: num1, num2, num3 = 0, 0, 1 for i in range(n): num1 = num2 num2 = num3 num3 = num1 + num2 return num3
