一、题目

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

二、分析及代码

1. 动态规划

（1）思路

动态规划基础题，因为一次可跳 1 或 2 级台阶，假设跳上第 n 级台阶跳法数为 F(n)，则 F(n) = F(n - 1) + F(n - 2)。
结果为斐波那契数列。

（2）代码

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

（3）结果

运行时间： 10 ms，占用内存 9560 k。

三、其他

暂无。