【算法题】12.爬楼梯问题

题目

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

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

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

示例:

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

解析：

爬n阶楼梯为（n-1）和（n-2）阶的和，可联想到 斐波那契数列,因此可以使用递归法解决这个问题。

在递归法的基础上优化，我们可以把每一步的结果存储在 memo 数组之中，每当函数再次被调用，我们就直接从 memo 数组返回结果。在 memo 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 n。 这个时候我们可以继续优化，使用动态规划法。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题不是互相独立的。

1. 开辟一个memo数组
2. 遍历[0-n]调用直到n阶楼梯，缓存置数组中。
3. 返回数组中索引的值。

复杂度分析：

时间复杂度：
空间复杂度：

代码

    int climbStairs(int n){
      int *memo = (int *)malloc(sizeof(int) * n); 
      
   
       if(n==1) return 1;
       for (int i = 0; i <= n; i++) {
           if (i <= 2)
           {
              memo[i] = i;
           }else{
              memo[i] = memo[i-1] + memo[i-2];
           }
           
       }
       return memo[n];
   
   }