题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
初步思考过程:经典递归,考虑递归树中重复节点所导致的重复运算
初步解答:用空间换时间,保存递归结果即可
class
Solution {
public
:
int
jumpFloorII(
int
number)
{
int
resultStore[100]={0};
resultStore[1]=1;
int
i=2;
while
(i!=number+1)
{
for
(
int
j=1;j<=i-1;++j)
{
resultStore[i]+=resultStore[j];
}
resultStore[i++]+=1;
}
return
resultStore[number];
}
};
用 vector resultStore(n+1,0)实现会更好一点,用于对付大规模数据
时间复杂度:O(n2)
空间复杂度:O(n)
重复节点示意,已f(7)为例
优化解法:
对待递归表达式类型的题目,应至少探求f(n),f(n-1),f(n-2)之间的关系,就像高中数学一样…
f[n] = f[n-1] + f[n-2] + … + f[0]
f[n-1] = f[n-2] + f[n-3] + … + f[0]
f[n]=2*f[n-1],f[1]=1;
故直接运算即可
代码如下:
int jumpFloorII(int n)
{
{
if (n==0 || n==1) return 1;
int a = 1;
for (int i=2; i<=n; ++i)
a = a << 1; // 口诀:左移乘2,右移除2
}
return a;
}
也可直接求2的n-1次方,同时考虑0为边界条件即可。