产品网站系统/百度电话人工服务
裴波那契数列问题和爬楼梯问题的解法（递归和动态规划）
1. 裴波那契数列概述
斐波那契数列指的是这样一个数列 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)，那么它的结构就是
3. 裴波那契数列的递归和非递归解法
3.1 递归解法
如果你之前看过二叉树的遍历，那就应该很容易理解上面这幅图，因为二叉树也是长这样子，二叉树的遍历同样也可以用递归去做。如果之前没有看过二叉树，那也没什么，等你会了这个裴波那契的递归过程，到时理解二叉树的遍历就会轻松很多。
我们需要明确，要想求第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);
}
其实这就是二叉树的后序遍历
3.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;}
}
4. 爬楼梯问题
4.1 普通的爬楼梯问题
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)，其实就是一个裴波那契数列，解法和裴波那契的解法完全一致！
4.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)为第一步的步数，第一步的步数不能大于总的台阶数iwhile(pow(2, tmp) <= i){//第一步的步数小于总的台阶数iif(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
5. 注意
当阶数n达到成百上千阶的时候，计算的结果会非常大以致于long类型也会溢出，可以对每一次得到的dp[i]值取模，dp[i] %= 1000000003这样子足够了