算法:跳台阶

跳台阶

跳台阶

一只青蛙一次可以跳上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;
    }
}