文章482
标签257
分类63

算法:跳台阶


跳台阶

跳台阶

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


分析

典型的动态规划

可以通过创建dp[]数组, 而dp[i]为跳上第i层台阶的跳法.

递推公式:

dp[1] = 1;

dp[2] = 2;

dp[i] = dp[i - 1] + dp[i - 2] (i > 2);

进一步分析即菲波那切数列.


代码

public class Solution {
    public int JumpFloor(int n) {
        if (n <= 0) return 0;
        if (n <= 2) return n;
        int f1 = 1, f2 = 2;
        for (int i = 3; i <= n; ++i) {
            int temp = f2;
            f2 += f1;
            f1 = temp;
        }
        return f2;
    }
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/1996/07/27/算法-跳台阶/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可