算法笔记_面试题_1.爬楼梯

灰太狼 2023-02-20 02:42 20阅读 0赞

# 题目 #

一个人爬楼梯，他可以一次走1阶或者2阶，输入不同的楼梯数，求有多少种不同的走法？

# 问题分析 #

从最后到达终点那阶考虑，记为F(n)， 则到达F(n)有两种情况， 从F(n-1)的位置，走1阶到达; 从从F(n-2)的位置，走2阶到达。所以 F(n) = F(n-1) + F(n-2); 即是fibonacci数列的情况。

# 递归法 #

int climbStairs(int n)
    {    
        if (n <= 0) return 0;
        return (n  == 1 || n == 2) ? n : climbStairs(n - 2) + climbStairs(n - 1);
    }

递归法：时间复杂度 O(2^n)

# 优良算法 #

#include <stdio.h>
    #include <iostream>
    
    int climbStairs(int n)
    {
        if ( n<=2 ) return n;	
    	
        int f1= 1, f2= 2, f3= 0;	
        for(int i=3; i<=n; ++i)
        {
        	f3 = f1+ f2;	
        	f1 = f2;
            f2 = f3;
        }	
    	return f3;
    }

测试代码:

int main(int argc, char* argv[])
    {
    	for( int n=-3; n<=10; ++n)
    	{
    		std::cout <<"n="<< n << ": " 
    			  << climbStairs(n) << std::endl;
    	}
    	return 0;
    }

输出结果：

![20200622185126368.png][]

## 复杂度分析 ##

*  时间复杂度：O(n), 因为只有一个单循环到n, 所以计算到第那个斐波那契数。
 *  空间复杂度：O(1), 没有使用任何数组或者矩阵之类的。常数级空间。

# 最优算法 #

*  求斐波那契数列的公式，直接带公式

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70][]

对应的C++ 代码：

#include <stdio.h>
    #include <iostream>
    #include <cmath>
    int climbStairs(int n)
    {
    	if (n<0) return 0;
    	double sqrt5 = sqrt(5);
    	double fibn = pow((1+sqrt5)/2,n+1) - pow((1-sqrt5)/2,n+1); //注意是n+1
    	return (int)(fibn/sqrt5); //注意后面要加括号！
    }

参考: [https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/][https_leetcode-cn.com_problems_climbing-stairs_solution_pa-lou-ti-by-leetcode-solution]

[20200622185126368.png]: https://img-blog.csdnimg.cn/20200622185126368.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200623224332513.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoeWpoeXAxMQ==,size_16,color_FFFFFF,t_70
[https_leetcode-cn.com_problems_climbing-stairs_solution_pa-lou-ti-by-leetcode-solution]: https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/