这题之前刷leetcode也遇到过,感觉是跟斐波拉契差不多的题。
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
解题思路:
这类题一般就是用递归思想,先考虑跳一级台阶情况,再是两级。发现由于跳台阶的选择只有1级和2级,所以其实跳n级台阶就是跳n-1级和n-2级的和。
本科做斐波拉契用递归时已经知道会超时,由于分别计算f(n-1)和f(n-2)实际是重复计算了,所以用数组去存每次的计算结果,直接调用就可以。
代码:
class Solution {public: int jumpFloor(int number) { vector sum_jump; sum_jump.push_back(0); sum_jump.push_back(1); sum_jump.push_back(2); for(int i=3; i<=number; i++) { sum_jump.push_back(sum_jump[i-1]+sum_jump[i-2]); } return sum_jump[number]; }};