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

2020-04-13  本文已影响0人  _涼城
题目

假设你正在爬楼梯。需要 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. 返回数组中索引的值。
复杂度分析:

时间复杂度: O(n)
空间复杂度: O(n)

代码
    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];
   
   }

上一篇 下一篇

猜你喜欢

热点阅读