09(2) 变态跳台阶 --《剑指Offer》(Java版)

红太狼 2022-03-10 08:56 129阅读 0赞

[github地址][github]

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

这道题的简化版本就是斐波那契数列.

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

通过简单的找规律就可以发现，第n层的可能性是前n-1层的可能性之和+1.

所以公式：f(n) = sum(f(1),f(2),,,,f(n-1)) + 1

然后一个递推就搞定了(千万别递归，如果递归一定要做好记忆化).

当然上面的时间复杂度还是O(n)，如果你写出来一个表.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70][]

哦呼，你就会发现更简洁的公式：f(n) = 2^(n-1)

/**
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     */
    public class _009_JumpFloorII {
        /**
         * 我们的第一反应：
         * 斐波那契数列。
         * 但是又感觉不太对，那么我们推导一下，
         * 每个算式最后的 + 1都是直接一步到位
         * f(1) = 1
         * f(2) = f(1) +1
         * f(3) = f(1) + f(2) + 1   // 可以从1爬到3，也可以从2爬到3，也可以直接到3
         * f(4) = f(1) + f(2) + f(3) + 1        // 规律很明显了
         * // 到以上，我们就发现了规律，可以编码了，但是更进一步的话，有惊喜。
         * f(1) =1,f(2) =2,f(3) = 4, f(4) = 8
         * f(5) = f(1) + f(2) + f(3) + f(4) + 1 // 如果我们把之前的四个都代入到f(5)会怎样根
         * f(5) = 16,
         * emm, 每一位都等于前n-1位的和+1.
         * 所以f(n) = 2^(n-1);
         */
        public int JumpFloorII(int n) {
            int res = 1;
            while (n-- != 1) {
                res <<= 1;
            }
            return res;
        }
    
    }

[github]: https://github.com/RudBob/offer66
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]: /images/20220310/fdd8b5a08f834aa48895e8f57005fe6c.png