title: leetcode-70-爬楼梯(java)

date: 2019-09-17 20:15:41

mathjax: true

categories:

• leetcode

  tags:

• leetcode

leetcode-70-爬楼梯(java)

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

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

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

  示例 1：

  输入： 2

  输出： 2

  解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶

  2. 2 阶

     示例 2：

  输入： 3

  输出： 3

  解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

  来源：力扣（LeetCode）

  链接：https://leetcode-cn.com/problems/climbing-stairs

  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

• 题解:说细节没意思，主要一句话：斐波拉契数列，f(n) = f(n-1)+f(n-2)
• 题解：递归，超时，因为分支太多，重复的太多了

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

• 递归不行，那就循环来凑

  class Solution {
      public int climbStairs(int n) {
          if(n==1||n==2)
              return n;
        int[] nums = new  int[n];
        nums[0] = 1;
        nums[1] = 2;
        for (int i=2;i<n;i++){
            nums[i] = nums[i-1]+nums[i-2];
        }
        return nums[n-1];
          
      }
  }
             

• 改进循环

  class Solution {
      public int climbStairs(int n) {
          if(n <= 2){
              return n;
          }
          int pre2 = 1, pre1 = 2;
          for(int i = 2; i < n; i++){
              int cur = pre1 + pre2;
              pre2 = pre1;
              pre1 = cur;
          }
          return pre1;
      }
  }
             

• 啥也不想写，好吧，上数学公式 F n = 1 / 5 [ 1 + 5 2 ) n − ( 1 − 5 2 ) n ] F_n=1/{\sqrt5}[{\frac {1+\sqrt 5}{2})^n−(\frac{1−\sqrt 5}{2})^n}] Fn​=1/5

  ​[21+5

  ​​)n−(21−5

  ​​)n]

  public class Solution {
      public int climbStairs(int n) {
          double sqrt5=Math.sqrt(5);
          double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
          return (int)(fibn/sqrt5);
      }
  }