使用递归和动态规划两种方式解决“青蛙跳台阶”问题

题目：青蛙跳台阶
描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：可以使用递归，循环（迭代）法或者动态规划法，这里主要讲下动态规划的思路。
动态规划：所谓动态规划，无非就是利用历史记录避免重复计算。而这些历史记录，我们需要一些变量来保存，通常是用一维数组或者二维数组来保存。

（1）定义数组元素的含义
首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样，如果我们能够算出 dp[n]，不就是我们要求的答案吗？所以第一步定义完成。
（2）找出数组元素间的关系式
题目的要求是求dp[n]，动态规划的题，如你们经常听说的那样，就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3…. 也就是说，dp[n] 一定会和 dp[n-1], dp[n-2]….存在某种关系的。我们要找出他们的关系。
那么问题来了，怎么找？
这个怎么找，是最核心最难的一个，我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？
对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式：
1）一种是从第 n-1 级跳上来
2）一种是从第 n-2 级跳上来
由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。
（3）找出初始条件
当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0.（因为 0 个台阶，那肯定是 0 种跳法了）。于是得出初始值：
dp[0] = 0. dp[1] = 1. dp[2] = 2. 即 n <= 2 时，dp[n] = n.
三个步骤都分析出来了，下面我们开始撸代码：

package od;

/**
 * 青蛙跳台阶
 * 问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 原文地址：https://www.codernav.com/2802.html
 */
public class OdTest01 {
    public static void main(String[] args) {
        System.out.println(f(10));
        System.out.println(f1(10));
    }

    /**
     * 递归法
     * 跳第n个台阶，只能从第n-1个台阶和第n-2个台阶跳，所以f(n)=f(n-1)+f(n-2)
     */
    private static int f(int n) {
        if (n <= 2) {
            return n;
        }
        return f(n - 1) + f(n - 2);
    }

    /**
     * 动态规划法 Dynamic Programming，DP
     */
    private static int f1(int n) {
        if (n <= 2) {
            return n;
        }

        int[] dp = new int[n + 1];
        // 动态规划一定要寻找对初始值，假设不设置dp[2]，打印出的值就是错的
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

总结：动态规划的3个步骤
第一步：定义数组元素的含义
第二步：找出数组元素之间的关系式
第三步：找出初始值