leetCode 070 爬楼梯

题目描述：

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

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

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

示例输入输出：

  1. 输入： 2
  2. 输出： 2
  3. 解释： 有两种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶
  5. 2.  2 阶
  7. 输入： 3
  8. 输出： 3
  9. 解释： 有三种方法可以爬到楼顶。
  10. 1.  1 阶 + 1 阶 + 1 阶
  11. 2.  1 阶 + 2 阶
  12. 3.  2 阶 + 1 阶

思路：

利用数组进行动态规划

  • 第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去。

  • 参数：

    • 辅助数组

  • 终止条件：

    • cur为null

  • 迭代过程中做的事：

    -

  • 复杂度分析：

    • 时间复杂度：只需要遍历一遍，O（n）
    • 空间复杂度：O（n）

  • 代码：

    1. /*
    2. 第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去。
    3. */
    4. class Solution {
    5.   public int climbStairs(int n) {
    6.       if(n < 2){
    7.           return n;
    8.       }
    9.       int[] f = new int[n+1];
    10.       f[1] = 1;
    11.       f[2] = 2;
    12.       for(int i = 3; i <= n; i++){
    13.           f[i] = f[i-1] + f[i-2];
    14.       }
    15.       return f[n];
    17.   }
    18. }

动态规划空间优化

  • 已知对于任意三个元素，第三个元素是前两个元素的和，可以仅用三个变量表示。

  • 复杂度分析：

    • 时间复杂度：只需要遍历一遍，O（n）
    • 空间复杂度：不需要额外的空间，O（1）

  • 代码：

  • class Solution {
  public int climbStairs(int n) {
      if(n < 2){
          return n;
      }
      int i1 = 1;
      int i2 = 2;
      for(int i = 3; i <= n; i++){
          int temp = i1 + i2;
          i1 = i2;
          i2 = temp;
      }
      return i2;
  }
}

斐波那契数列通解

数学方法，懒得记