题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
大致思路
- 反向推导,要跳到 n 级台阶,那么跳之前就有两种情况:在 n-1 级和在 n-2 级台阶的位置。那么假如 f(n) 表示跳到 n 级台阶的跳法,那么则有 f(n) = f(n-1) + f(n-2)。
- 是不是很熟悉了,它就是上一题的斐波那契数列的表达形式啊。
代码
int jumpFloor(int number) { if (number <= 2) return number; int before_1 = 1, before_2 = 1, result = 0; for (int i = number; i > 2; --i){ result = before_1 + before_2; before_2 = before_1; before_1 = result; } return result;}复制代码
总结
这样的解法一样避免了大量迭代和重复的计算过程。动态规划!