台阶很高，青蛙跳不跳？

niejunlei 2020-07-01 原文

青蛙总是被被要求跳台阶，我想，他一定很累的！

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

对于这样的问题，n可大可小，如果n很小，我们可以直观暴力拆解就可以得到答案，但是如果n很大，那么这个问题就升级了。

一般处理问题，我们最直接的思路，可能就是分治，将大问题拆解为小问题，分而解决。

在此，也不例外。

首先我们知道青蛙一次能跳一级或者两级。

假定最后一跳跳一级，则剩余n-1个台阶，则问题化为解决跳上n-1个台阶的问题。

假定最后一跳跳两级，则剩余n-2个台阶，则问题化为解决跳上n-2个台阶的问题。

所以归总起来，总的可能的跳法为（n-1）个台阶和（n-2）个台阶问题的总和。

我们假定解决方案为f(n)，则f(n) = f(n-1) + f(n-2) ，这里我们假定n是大于2的。

当n = 1 时，青蛙跳一级即可，f(1) = 1。

当n = 2 时，青蛙可以连跳两个一级或者跳一个两级，f(2) = 2。

观察f(n) = f(n-1) + f(n-2) 公式，你们首先想到的是什么？对的，是递归，级联求解：

 public static long jump(int n) {
        if (n < 3) {
            return n;
        }

        return jump(n - 1) + jump(n - 2);
    }

我们以图像化展示一下这个过程：

图中以相同颜色标识了递归过程中会产生重复计算的节点。

重复是一种算力和资源不必要的浪费，我们可以对此进行优化：

对于上述的递归运算，我们可以看到，是由后至前计算的，也即从f(n)->f(1)。也就是我们需要知道向前的每一个位置的方案结果。我们换个方向，从前至后连续计算出每个位置的方案，则最后的位置即为我们所要的结果，同时也可以规避重复计算的问题：

代码实现：

public static long jumpx(int n) {
        if (n < 3) {
            return n;
        }

        //每个位置存储下标（i + 1）个台阶的可能结果f(i + 1)，所以n个台阶即为计算f(n - 1)
        Long[] arr = new Long[n];
        arr[0] = 1L; //一个台阶
        arr[1] = 2L; //两个台阶
        //从 n = 3 开始循环计算
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n - 1];
    }

我们通过增加一个长度为n的数组空间占用来换取算法耗时优化，相对于递归算法，耗时上有数量级差别。

耗时减少了，但是空间似乎浪费了，其实，也没必要存储每一个方案的结果，我们只需要知道【前一个】，【前两个】以及【当前】的几个变量。

改造如下：

public static long jumpy(int n) {
        if (n < 3) {
            return n;
        }

        //第三节台阶方案值f(3) = f(2) + f(1) = 1 + 2 = 3;
        long preTwoCount = 1; //一个台阶
        long preOneCount = 2; //两个台阶
        long stepsCount = 0; //n个台阶
        //从 n = 3 开始循环计算
        for (int i = 2; i < n; i++) {
            stepsCount = preOneCount + preTwoCount;
            preOneCount = stepsCount;
            preTwoCount = preOneCount;
        }
        return stepsCount;
    }