LeetCode 70.爬楼梯

向右看齐 2023-07-17 15:42 12阅读 0赞

**第一种解法：斐波那契数F(n)=F(n-1)+F(n-2)**

**时间复杂度O(n) 空间复杂度O(1)**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E2NjY2Nl8_size_16_color_FFFFFF_t_70][]

>  
> 
> java写法
> 
> 第一种：
> 
> public int climbStairs(int n) \{
> 
>         if (n <= 3) \{
> 
>             return n;
> 
>         \}
> 
>         int f1 = 2, f2 = 3, f3 = 0;
> 
>         for (int i = 4; i < n + 1; ++i) \{
> 
>             f3 = f1 + f2;
> 
>             f1 = f2;
> 
>             f2 = f3;
> 
>         \}
> 
>         return f3;
> 
>     \}
> 
> 第二种(与第一种相比只是2变成了3)
> 
> class Solution \{
> 
>     public int climbStairs(int n) \{
> 
>         if (n <= 2) \{
> 
>             return n;
> 
>         \}
> 
>         int f1 = 1, f2 = 2, f3 = 0;
> 
>         for (int i = 3; i < n + 1; ++i) \{
> 
>             f3 = f1 + f2;
> 
>             f1 = f2;
> 
>             f2 = f3;
> 
>         \}
> 
>         return f3;
> 
>     \}
> 
> \}
> 
> C++解法
> 
>  int climbStairs(int n) \{
> 
>         if (n <= 2) \{
> 
>             return n;
> 
>         \}
> 
>         int f1 = 1;
> 
>         int f2 = 2;
> 
>         int f3 = 3;
> 
>         for (int i = 3; i < n + 1; ++i)\{
> 
>             f3 = f1 + f2;
> 
>             f1 = f2;
> 
>             f2 = f3;
> 
>         \}
> 
>         return f3;
> 
>     \}

第二种解法：斐波那契数递归解法**F(n)=F(n-1)+F(n-2)**

**时间复杂度O(2^n) 空间复杂度O(n)**

>  public int climbStairs(int n) \{
> 
>         if (n == 1 || n == 2) \{
> 
>             return n;
> 
>         \}
> 
>         return climbStairs(n - 1) + climbStairs(n - 2);
> 
>     \}

第三种解法：动态规划

**时间复杂度O(n) 空间复杂度O(1)**

> C++描述：
> 
> int climbStairs(int n) \{
> 
>         int a = 1, b = 1;
> 
>         while (--n > 0)\{
> 
>              a = (b += a) - a;
> 
>         \}
> 
>         return b;
> 
>     \}
> 
> JAVA描述
> 
>  public int climbStairs(int n) \{  
>         int a = 1, b = 1;  
>         while(--n > 0)\{  
>             b = a + b;  
>             a = b - a;  
>         \}  
>         return b;  
>     \}

第四种解法：斐波那契公式

>  public int climbStairs(int n) \{
> 
>         double sqrt\_5 = Math.sqrt(5);
> 
>         double fib\_n = Math.pow((1 + sqrt\_5) / 2, n + 1) - Math.pow((1 - sqrt\_5) / 2,n + 1);
> 
>         return (int)(fib\_n / sqrt\_5);
> 
>     \}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E2NjY2Nl8_size_16_color_FFFFFF_t_70]: /images/20230528/10791b34bb2e46a69ca13a8d8c123fb3.png