外观
[算法]楼梯台阶斐波那契数列问题
上周去笔试，在笔试题中看到了这道算法题，基本上没怎么考虑，就直接跳过了。现在想来着实是懊悔的要死。今早又回顾了这道题的细节和实现，现做笔记，以备后日复习。
二、算法描述
现有n级台阶，每次可以走1步，也可以走2步。问一共可以有多少种走法？并给出相应算法的时间和空间复杂度？
三、解题思路
针对问题描述，对n从1到5做一个结果举例，根据结果寻找规律。
n=1：
走法：1
种类：1
n=2：
走法：1 1、2
种类：2
n=3：
走法：1 1 1、1 2、2 1
种类：3
n=4：
走法：1 1 1 1、1 1 2、1 2 1、2 1 1、2 2
种类：5
......基于上述结果，可得出以下规律(n >= 3)，也就是斐波那契数列，后续的代码实现均以此为基础进行实现：
F(n) = F(n-1) + F(n-2)四、代码实现
/**
* 斐波那契数列数列问题
*
* @author liuwanxiang
* @version 2019/06/18
*/
public class FibonacciSequence {
/**
* 案例一：n节台阶，每步可1可2，问有多少中解法？
* 时间复杂度及空间复杂度各为多少？
*
* 递归实现
* 时间复杂度：O(n) = 2 ^ n
* 空间复杂度：O(n) = n
*
* @param n 多少级台阶
* @return 走法
*/
private static int stepV1(int n) {
if (n == 1 || n == 2) {
return n;
}
return stepV1(n - 1) + stepV1(n - 2);
}
/**
* 非递归实现
* 时间复杂度：O(n) = n
* 空间复杂度：O(n) = 1
*
* @param n 多少级台阶
* @return 走法
*/
private static int stepV2(int n) {
if (n == 1 || n == 2) {
return n;
}
int n1 = 1;
int n2 = 1;
for (int i = 2; i < n; i++) {
n2 = n1 + n2;
n1 = n2 - n1;
}
return n1 + n2;
}
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
System.out.println(stepV1(i));
System.out.println(stepV2(i));
}
}
}版权所有
版权归属：Wanxiang Liu