LeetCode 70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

解题思路： n=1时，方法有1种 n=2时，方法有2种 n=3时，方法有3种 n=4时，方法有5种 可得递推式F(n) = F(n-1) + F(n-2)，类似于斐波那契数列。

解法一:递归，这个递交显示超出时间限制 时间复杂度O(2ⁿ),空间复杂度O(n)

int climbStairs(int n) { if (n == 1) { return 1; } else if (n == 2) { return 2; } else { return climbStairs(n - 1) + climbStairs(n-2); } }

解法二：动态规划 时间复杂度O(n),空间复杂度O(n)

class Solution { public: int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int i; int *result = new int[n]; result[0] = 1; result[1] = 2; for(i = 2; i < n; i++){ result[i] = result[i - 1] + result[i - 2]; } int way = result[n - 1]; delete[] result; return way; } };

解法三：滚动数组： 时间复杂度O(n),空间复杂度O(1)

class Solution { public: int climbStairs(int n) { if(n == 0 ||n == 1) return 1; int step0 = 1; int step1 = 1; int step; for (int i = 2; i <= n; i++){ step = step0 + step1; step0 = step1; step1 = step; } return step; } };