2
算法系列：斐波那契数列问题 - FOEVERYANG
source link: https://www.cnblogs.com/lsgspace/p/16894372.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
问题描述：
假设有个楼梯，每次只能走3步或者5步，问到达第N节会有几种组合？
思路分析：
这个问题需要反过来思考才能比较容易的找到规律。总共有N级台阶，因为每次要么上3阶要么上5阶，因此对于第N级台阶来说，它的前一步要么是在N-3阶处要么是在N-5阶处。在N-3阶处时上3阶到N级台阶，在N-5阶处时上5级到N级台阶。因此，可以用公式表示为f(n)=f(n-3)+f(n-5)，这就变成了一个典型的递归了。像这种公式，在数列中有一个比较著名的数列叫做“斐波那契数列”，当然这里是3和5可以看做是一种变形的“斐波那契数列”；如果把3和5变成1/2就是完美的斐波那契数列了；
补充：斐波那契数列是满足F(n)=F(n-1)+F(n-2) 的数列
好了既然分析出规律了，那么我们用代码实现以下
方法一：递归实现
时间复杂度：O(!n)
public static int countStep(int n) {
if (n < 3) { //当n小于最小阶数时，没有可能的方案
return 0;
} else if (n == 3) { //当前值等于3时.只有一种可能
return 1;
} else if (n > 3 && n < 5) {//当前值大于3并且者小于5时.没有可能的方案
return 0;
} else if (n == 5) { //当n==5时只有一种可能
return 1;
} else { //n>5时，采用递归的方式进行计算
return countStep(n - 3) + countStep(n - 5);
}
}
方法二：动态规划
方法一种的单纯递归的时间复杂度过高，我们可以将之前计算过的结果存放到map中，如果之后map中存在则直接获取；
public static int climbStairs(int n, Map<Integer, Integer> map) {
if (n < 3) { //当n小于最小阶数时，没有可能的方案
return 0;
} else if (n == 3) { //当前值等于3时.只有一种可能
return 1;
} else if (n > 3 && n < 5) {//当前值大于3并且者小于5时.没有可能的方案
return 0;
} else if (n == 5) { //当n==5时只有一种可能
return 1;
} else if (map.containsKey(n)) {//若Map中已经存在之前的计算结果，则直接从map中获取
return map.get(n);
} else { //n>5时，采用递归的方式进行计算
int temp = climbStairs(n - 3, map) + climbStairs(n - 5, map);
map.put(n, temp);
return temp;
}
}
上述动态规划在n比价小的时候并不能体现其优势，但当n较大时，就有可一避免出现多处的重复计算的情况，较少时间复杂度；
拓展思考：
变形一：每次能走3阶、5阶、7阶时，有多少种可能？
思路：F(n)=F(n-3)+F(n-5)+F(n-7)
变形二：每次最多走M阶，问走到N阶有多少种可能？
思路：F(n)=F(n-1)+F(n-2)+F(n-3)……F(n-m)
public static int countM(int n, int m, Map<Integer, Integer> map) {
int count = 0;
if (n == 0) {
return 1;
}
if (map.containsKey(n)) {
return map.get(n);
} else if (n >= m) {
for (int i = 1; i <= m; i++) {
count += countM(n - i, m, map);
}
} else {
count += countM(n, n, map);
}
map.put(n, count);
return count;
}
总结：该算法是对菲波那切数列的应用，一般情况下,一旦能用数列的形式表示某种关系那么最先想到的就是递归。该题的难点是能够找到递归规律以及在递归中各种数值的划分。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK