赞
踩
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368…这个数列从第3项开始,每一项都等于前两项之和。
所以它的通式就是 f(n) = f(n-1) + f(n-2) {条件是n >= 3},假如我只知道f(1)和f(2),要求第5项 f(5),那么它的结构就是
如果你之前看过二叉树的遍历,那就应该很容易理解上面这幅图,因为二叉树也是长这样子,二叉树的遍历同样也可以用递归去做。如果之前没有看过二叉树,那也没什么,等你会了这个裴波那契的递归过程,到时理解二叉树的遍历就会轻松很多。
我们需要明确,要想求第f(n)项就必须要知道f(n-1)和f(n-2)项,所以递归的话一句代码就能搞定
public static int f(n){
return f(n - 1) + f(n - 2);
}
哈哈,但是递归的话,你要让它知道应该在哪里结束呀,不然就死循环了,上面的代码中明显就没有结束条件!
仔细对着我上面画的那副图分析,我一直画到已知条件f(2)和f(1)就没往下画了,就说明以f(5)为起点开始分支,以f(2)和f(1)为终点,因为f(2)和f(1)是已知条件,所以代码就出来了
public static int f(n){
if(n == 1 || n == 2){
return 1;
}
return f(n - 1) + f(n - 2);
}
其实这就是二叉树的后序遍历
当n超过30的时候,递归解法将非常耗时,非常耗内存,所以不推荐使用递归的解法,下面是非递归的代码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //输入要求第几项 int n = sc.nextInt(); long res = f(n); System.out.println(res); } //求裴波那契数列 private static long f(int n) { if(n == 1 || n == 2){ return 1; } long tmp1 = 1; long tmp2 = 1; long res = 0; //第一项就是tmp1 = 1, 第二项就是tmp2 = 2,所以从第三项开始算 for (int i = 3; i <= n; i++) { res = tmp1 + tmp2; tmp1 = tmp2; tmp2 = res; } return res; } }
LeetCode70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
首先,我们的第一步有两种可能,可以选择爬1个或2个台阶:
①:如果我们第一步爬1个台阶,那还剩下n-1个台阶,剩下的n-1个台阶的爬法是f(n - 1)
②:如果我们第一步爬2个台阶,那还剩下n-2个台阶,剩下的n-2个台阶的爬法是f(n - 2)
所以总的爬法 f(n) = f(n - 1) + f(n - 2),其实就是一个裴波那契数列,解法和裴波那契的解法完全一致!
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 2的n次幂个台阶。即每次可以爬1、2、4、8、16…你有多少种不同的方法可以爬到楼顶呢?
还是同样的分析,我们先分析第一步有多少种可能
①:如果我们第一步爬1个台阶,那还剩下n-1个台阶,剩下的n-1个台阶的爬法是f(n - 1)
②:如果我们第一步爬2个台阶,那还剩下n-2个台阶,剩下的n-2个台阶的爬法是f(n - 2)
③:如果我们第一步爬4个台阶,那还剩下n-4个台阶,剩下的n-4个台阶的爬法是f(n - 4)
④:如果我们第一步爬8个台阶,那还剩下n-8个台阶,剩下的n-8个台阶的爬法是f(n - 8)
④:如果我们第一步爬16个台阶,那还剩下n-16个台阶,剩下的n-16个台阶的爬法是f(n - 16)
…
究竟要分析到哪里结束呢?假如我要求9阶时的爬法,那第一步总不能爬16个台阶吧,因为我本身只有9个台阶,怎么能一步就爬16个台阶呢,但是我第一步可以爬8个台阶,所以第一步的步数step不能大于总的阶数n。
这就是传说中的动态规划思想呀
import java.util.Scanner; import static java.lang.Math.pow; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] dp = new long[n + 1]; dp[0] = 0; dp[1] = 1; //当台阶只有1的时候,走法只有1种 dp[2] = 2; //当台阶只有2的时候,走法只有2种 for(int i = 3; i <= n; i++){ int tmp = 0; //pow(2, tmp)为第一步的步数,第一步的步数不能大于总的台阶数i while(pow(2, tmp) <= i){ //第一步的步数小于总的台阶数i if(pow(2, tmp) < i){ //假如第一步爬的阶数是pow(2, 0) = 1,那么还剩i - 1个台阶,走法为dp[i-1] dp[i] += dp[i - (int) pow(2, tmp)]; } //第一步的步数等于总的台阶数i,那么一步就走完了,所以只有一种走法 else if(pow(2, tmp) == i){ dp[i] += 1; } tmp++; } } System.out.println(dp[n]); } }
牛客网就有这么一道题:魔法深渊
题目链接:https://www.nowcoder.com/practice/55e34723b1d34c42af83b39de2395408?tpId=98&tqId=32842&rp=2&ru=%2Fta%2F2019test&qru=%2Fta%2F2019test%2Fquestion-ranking&tPage=1
当阶数n达到成百上千阶的时候,计算的结果会非常大以致于long类型也会溢出,可以对每一次得到的dp[i]值取模,dp[i] %= 1000000003这样子足够了
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。