题目:一只青蛙一次可以跳上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为边界条件即可。