题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

初始代码

class Solution {
public:
    int jumpFloorII(int number) {

    }
};

解法1

本题牛客网给了一个“贪心”的标签， 在在做这道题之前， 首先就被它的阵势给吓住了。。。什么“变态”啦， 什么“贪心”算法啦。脑子里一直在想贪心是个什么样的定义，最优子结构？还有什么？本题的最优子结构又是体现在哪里？
题目还未开始动，自乱阵脚是一件比较可怕的事。
最好的解决办法还是先动手动脑，看看能有什么样的解题思路。不要被这个纸老虎给挡住去路啦。

青蛙一次可以跳1~n级，在题目中我们最终需要跳n级，那么还是顺着[JZ8]跳台阶一题的思路，我们首先关注最后一跳。
现在青蛙有了多种选择，最后一跳可以只跳了1级，也可以跳了2到n中的任意一个数值的级数。
使用表达式抽象出来就是：f(n) = f(n-1) + f(n-2) + ... + f(1) + 1。

这个表达式很有特殊性。
它也作为一个递归式，其递归出口是f(1) = 1。
因此我们可以轻易地得到：

f(2) = f(1) + 1 = 2
f(3) = f(2) + f(1) + 1 = 4
...

在代码实现中，就遵照这个思路给出答案。由于如果从底向上计算，那么计算f(k)的时候，f(k-1)到f(1)之间的值其实都是计算过的。可以考虑使用一个数组来保存之前计算过的值，从而避免计算的重复，提高效率。
例如，使用一个长度为number-1的整型数组nums，最开始我们只知道nums[1] = 1，然后我们从i=2开始一直到i=number，每计算一次就把结果保存在nums[i]中，从而避免了了在计算下一个数的时候还重复计算前面的。

但其实在此基础上还有个明显的优化点。那便是我们在递归式中其实并不关注每个前面的值具体是多少，例如当计算f(i)时，我们真正关注的是f(1)+f(2)+...+f(i-1)这个和式的值是多少，至于和式中每个分量的值是多少并不需要知道。
因此，我们对上面的思路进一步优化，不再开辟一个数组来保存每一个f(i)，i=1,2,...,n。只需一个变量来保存迄今为止f(1)+f(2)+...+f(i-1)这个和式的值sum，另外一个变量就基于sum的值来计算得到f(i)，即f(i)=1+sum。

下面是代码：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1) return number;

       int sum = 0, res = 1;

       for(int i=2; i <= number; i++)
       {
           sum = 1 + res;
           res += sum;
       }
        return sum;
    }
};

解法2

解法1整个思路下来并没有多费脑筋，而最开始萦绕在脑海中的“贪心”标签，也没有很体会到贪心在哪，或许我这个解法不是贪心？

查找已有的题解，看是否有“贪心”策略，但发现置顶的官方题解中都没有特别提到“贪心”的使用。那就不纠结了吧，日后遇到典型的通过贪心来解决的题目的时候再来回顾本题，看是否有新的理解。

官方题解中透露了一个在解法1上的进一步优化策略。上面已经得到：

f(n) = f(n-1) + f(n-2) + ... + f(1) + 1；（1）

那么也同时有：

f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1； （2）

（1）式减去（2）式再移项，得到：

f(n) = 2 * f(n-1)； （3）

!!!

所以说，本题归结到底就是一个二乘递归式咯？
接着就可以根据式（3）建立递推来得到一个新的解法；
同时，也可以更进一步地，推导出：f(n) = 2^(n-1)

两种思路的代码实现如下：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1) return number;

        return jumpFloorII(number - 1) * 2;
    }
};

class Solution {
public:
    int jumpFloorII(int number) {
        return 1 << (number - 1);
    }
};