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);
      }
  }