题目

牛客网 - 跳台阶

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

思路

斐波那契数列，其实就是靠着前一个状态和前二个状态，推出了下一个状态

public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

此时，可以发现，空间是可以压缩的，因为一个状态，只跟前两个状态有关系，之前的都不需要了

public class Solution {
    public int JumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        // 前一个状态 & 前二个状态
        int p1 = 1;
        int p2 = 2;
        int result = 0;
        for (int i = 3; i <= target; i++) {
            // 求结果
            result = p1 + p2;
            // 状态分别后移
            p1 = p2;
            p2 = result;
        }
        return result;
    }
}

总结

有很多种变种问法

• 比如一次性可以跳1级，3级的，怎么算？若一次性可以跳 N 级呢？（牛客网 - 变态跳台阶）
• 例如，抽奖，一次抽一次，结果可以为抽到一元或二元，要凑 x 元，有多少种凑法？（老虎集团 2020 春招笔试第二场）
• 例如，母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年后又可以生小母牛。求 N 年后牛的数量（奶牛生产问题）

这次老虎证券笔试第二道就是抽奖题，而之前在奇安信笔试的第二道也是兔子问题，其实也都是这类问题

老虎的笔试一看还以为是数学题，吓了一跳，要没时间了才发现是斐波那契数列。。。写完后也不知道对不对，在这里再刷一遍，验证看起来是对的