题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
数据范围:1≤n≤40
要求:时间复杂度:O(n) ,空间复杂度: O(1)
示例:
输入:
2
返回值:
2
说明:
青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2
解题思路:
本题考察算法-动态规划算法的使用。用四种逐优的解法,来一步步发现动态规划算法的优势。
解法一:递归法。青蛙可以一次跳一阶也可以跳两阶,假设跳到n阶时的方案数为F(n),那么跳到n-1阶的方案数再加一就能跳到n阶,跳到n-2阶的方案数再加二也能跳到n阶,则跳到n阶的方案数是它们的和,即F(n)=F(n-1)+F(n-2),初始条件n小于等于1时,方案数为1,用递归很容易实现。时间复杂度O(2^n),因为每次调用jumpFloor,都要继续调用两次jumpFloor,这个复杂度是很高的;空间复杂度是递归栈空间,递归次数很大时,空间复杂度也是很高的。该方法虽然很容易写且理解,但是最不实用。
解法二:改进递归法。在解法一中不难发现,jumpFloor在执行过程中进行了大量的重复工作,比如计算F(5)时计算过F(4)和F(3),但计算F(6)时又计算了多遍,那如果用数组存好F(x)的数值,只要计算一次就足够了,再次调用只需要读取数组数据即可。这样时间复杂度降到了O(n),空间复杂度变为O(n)和递归栈空间。
解法三:动态规划。动态规划是在计算过程中,不断分析每一步的最优解,当进行到最后一步时,结果自然得出。如果说递归法是从后往前,那么动态规划就是从前往后。节省了递归栈空间。本题目简单,用一个循环即可完成,时间复杂度和空间复杂度均为O(n)。
解法四:改进的动态规划。解法三中空间复杂度还是太高,考虑到我们只需要求最终的结果,所以中间过程的数据并不需要保存下来,那么可以优化掉数组,用变量来动态存储F(n-1)和F(n-2)即可,时间复杂度为O(n),空间复杂度为O(1)。
测试代码:
解法一:递归法
class Solution { public: int jumpFloor(int number) { if (number <= 1) return 1; return jumpFloor(number-1)+jumpFloor(number-2); } };
解法二:改进递归法
class Solution { public: int data[100]{0}; int jumpFloor(int number) { if (number <= 1) return 1; if(data[number]>0) return data[number]; else data[number]=jumpFloor(number-1)+jumpFloor(number-2); return data[number]; } };
解法三:动态规划
class Solution { public: int data[100]{0}; int jumpFloor(int number) { data[0]=1; data[1]=1; for(int i=2;i<=number;++i) data[i]=data[i-1]+data[i-2]; return data[number]; } };
解法四:改进的动态规划
class Solution { public: int jumpFloor(int number) { int a=1,b=1,c=1; for(int i=2;i<=number;++i) { c=a+b; a=b; b=c; } return c; } };