文章524
标签277
分类67

算法:跳台阶


跳台阶

跳台阶

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


分析

典型的动态规划

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

递推公式:

dp[1] = 1;

dp[2] = 2;

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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/cn/1996/07/27/%E7%AE%97%E6%B3%95-%E8%B7%B3%E5%8F%B0%E9%98%B6/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可