题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路

一，正确定义问题（问题的解构），正确定义要求可以将问题n拆解为小规模问题n-1以及更小n-2等等，问题定义的不好会导致无法拆解或者用同等定义拆解小规模问题发现不是全局性的（在全局最优问题里尤甚：整数划分、矩阵连乘最小运算次数...）则不是正确的拆解。
第一个参考依据是后续遍历思路，就是先顺着从最基本的模拟解几步问题，然后知道大致流程后倒着解问题：这里是跳台阶：
先顺着是我从0阶开始可以跳到1也可以跳到2，跳一次就扩展出了两个可能的分支，跳第二次从1开始可以跳到2也可以到3，从刚才的2开始可以跳到3也可跳到4，即第二次会有2^2=4种尝试，但其中跳到3重复了2次，若一直顺着解要跳n我一定要把前面1到n-1的过程都模拟完才行因为n之前的任何一步都有可能到达n而每一条都是算入计数的，这里只是了解问题流程。
然后倒着解：如果现在直接就要第n步的跳法种类数，前面已经说了要经过1到n-1才能知道，关键信息就是还n还不能知道，递归的一个思想就是不知道的条件我也可以当作知道，反正他没有他自然会去调用到这些条件出现了才进行操作，带来的好处：

  • 1.是函数结构在解读上更加直观，问题是规模为n的情况我就定义问题为f（n）而不是从1到n一直推过来。然后稍加整理就会发现这就是后续遍历（严格是二叉树里面的说法，这里只是表这个意思）的结构，即真正求值实在所有分支遍历完完后才对本层次进行求解用所有分支的结果。
  • 2.（自己总结，可能有不对）在全局最优问题中，一旦希望子问题也是全局最优而不是局部最优，那么子问题也是个全局问题（最常见的问题定义不好就是按照定义拆解子问题发现他不是全局而是局部最优的，那就是按贪心来但贪心大多时候不是最优解, 以后补充例子），那么要实现子问题也是最优的结构，后续遍历结构是尤其合适的，刚才说后续遍历是现在不知道的条件也当场知道拿来用，在函数结构里他是拿那些条件来用了（那些条件的来源他们自己解决我这个层次不用管），实际他们就是继续调用下去，这一层一直在等他们的结果到来，在我这个函数里我一直等到他们会来才进行处理，所以他们回来的时候已经是跑到问题的最底部即吧整个问题跑了一遍，这时他的结果才是全局的，而我才能拿他们的结果作为当前的判断依据还能保证我处理出来的依旧是全局的。这就是说问题要倒着解——即后续遍历结构的原因。

第二个参考依据关于即使知道要用后续遍历了那具体到底该怎么解构问题，即找到f（n）和小规模的f（n-1）甚至是f（n-2）...之间的关系（这里不要局限在f（n）一定是由f（n-1）解决的，在卡特兰系列里会发现是由所有子代孙代规模的问题共同解决一个f（n）），参考依据（不是一定，只是没思路时提供借鉴）是到达问题f（n）的路径，这个跳台阶第n阶是怎么跳来的，他每次只能挑一步或者两步，所以到n只有n-1和n-2这两个规模的问题可以接着过来即只有两条路径，且每一个规模的问题都只有这两条路径（走棋格类的右上点只有左和下两条路）。

所以到这里得到一条叫状态转移方程的东西（dp里面最核心）dp（n）=dp（n-1）+dp（n-2），不同问题可能不是+，可能是其他操作如max/min，也可能不知n-1和n-2。参考这个方程可以用后续遍历思路做第一版的解答。

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int jumpFloor(int number) {
        return recursion(number);
    }
    int recursion(int n){
        if(n == 1)
            return 1;
        if(n == 0)
            return 1;
        return recursion(n-1)+recursion(n-2); //分解子问题不一定是n-1的情况，由卡特兰系列知可能为所有子孙规模问题的处理，
    }                                         //一个参考依据是可达问题n的路径，这里只有n-1和n-2两条，要划分好无漏无重
};

二.用空间去除重复计算，拿空间换时间。上面这个版本其实就是后续遍历的递归，其实在时间和空间上跟刚才说的顺着解决问题应该是没有差别的。那为什么还要这么做？1.是因为刚才说的全局最优解问题，顺着子问题很难分解为全局最优情况 2.顺着和倒着都有一个问题就是重复计算，f（4）需要f（3）和f（2），这时他们还没有3和2的所以会去计算，然后算好后，f（3）=f（2）和f（1），会发现都有f（2），但刚才的f（2）并没有保存，于是这就提供了优化的可能，将已经计算过的东西保存下来，拿空间换时间。而顺着做很多时候的重复无法统计（例子以后举），于是做第二版本解答：

class Solution_v2 {
public:
    vector<int> record;         //用空间换时间，在第一版上最直白的dp
    int jumpFloor(int number) {
        for(int i=0;i<number;++i)//
            record.push_back(-1);
        return recursion(number);
    }
    int recursion(int n){
        if(n == 1)
            return 1;
        if(n == 0)
            return 1;            //用空间节省重复计算（递归规模的重复是很可观的）
        return ((record[n-1]!=-1)?record[n-1]:recursion(n-1)) + ((record[n-2]!=-1)?record[n-2]:recursion(n-2));
    }
};

三，重新按照顺着的方向，但并不是说顺着做。上面这个其实oj没给过因为估计用了很大规模的样例，开的空间太大超过oj限制了。前面已经倒着做然后还用空间换取时间，现在再考虑：我求n我是倒着求n-1和n-2，n-1和n-2又各种按照同样的套路去做，就这样自动的往底层跑直到跑到出口（递归都会有个出口）1和0的情况（也可以是1和2），那么如果我还是倒着做，我现在不从n了我从2开始倒着做，很容易得出答案因为0和1都有了，此时2记录下来，然后再倒着求3，因为0，1，2都有了所以也很好求（省去了重复计算了，他们都求出来且存下来了）以此类推。注意的是这并不是顺着做的思路。
顺着：      逆着：     第三种：
->             <-       <-
->->         <-<-       <-<-
->->->     <-<-<-       <-<-<-
...         ...            ...
而且这种带来的好处时有时候原本需要的记录空间都可以精简如下例子原本为n个辅助空间精简为2个。

class Solution_v3 {
public:
    int n0=1, n1=1;             //更精简的dp，这里是线性的且只需要常备的两个元素就够了，并且直接自底向上dp，基本所以的都可以按照这三个步骤
    int jumpFloor(int number) { //会发现这里就是Fibnaci
        for(int i=1;i<number;++i){
            int tempt = n1;
            n1 = n0 + n1;
            n0 = tempt;
        }
        return n1;
    }
};

最后会发现这其实是个Fibnaci数列。此外这是个一维线性辅助空间的dp，还有很多辅助空间是二维表格的。
所以从篇幅上就知道最主要的是在第一步解决怎么定义问题即问题的解构上面。
最后其实还有一种排列组合解法（以前最容易陷入的做法），因为只能分解为2和1，所以其实就是先分类有多少个2的情况，然后接着按照每一种的个数求全排列然后去重（2的重复个数和1的重复个数），暂无做。