描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路

跳 1 个台阶，有一种跳法；跳 2 个台阶，有两种跳法；跳 3 个台阶，有三种跳法；跳 4 个台阶，有五种跳法；跳 5 个台阶，有八种跳法......

不知道大家发现啥规律没，从第三个台阶开始，每个台阶的跳法数量就是前一个和前两个台阶的跳法总和。
其实这个也很好理解，咱们想想，我要跳到一个台阶其实只有两条路，一个是从前一个跳过来；另一个就是从前两个台阶跳过来。那么该台阶的跳法自然就是前两个台阶的跳法总和了。
看看是不是这个道理。有了思路了这道题就好写了。

AC代码

方法一

public int jumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        // dp 数组，用来存储结果
        int[] dp = new int[target];
        // 第一个台阶是 1
        dp[0]  = 1;
        // 第二个台阶时 2
        dp[1] = 2;
        for (int i = 2; i < target; i ++) {
            // 通过公式推导
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // 返回第 target 个台阶的跳法
        return dp[target - 1];
    }

时间复杂度：O(n),n 为台阶数，每个台阶要遍历一遍
空间复杂度：O(n),n 为台阶数，每个台阶对应跳法数量要存储起来。

方法二

这个其实每次还要记住前两个台阶的数量就可以，那么咱们就不需要用存储
所有的台阶的跳法数量，只需要存储前两个就可以。

public int jumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        // 第一个台阶是 1
        int dp_1 = 1;
        // 第二个台阶是 2
        int dp_2 = 2;
        // 开始遍历
        for (int i = 3; i <= target; i ++) {
            // 获取前两个台阶总和
            int temp = dp_1 + dp_2;
            // 迭代
            dp_1 = dp_2;
            dp_2 = temp;
        }
        return dp_2;
    }

时间复杂度：O(n),n 为台阶数，每个台阶要遍历一遍
空间复杂度：O(1)

最后

这道题是最基础的动态规划算法题，这道题能让咱们入门动态规划，之后我也会由浅入深的继续和大家探索动态规划。让其不太神秘。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。