[剑指 Offer 第 2 版第 10 题] “变态跳台阶”做题记录

第 10-2 题：变态跳台阶

传送门：牛客网：变态跳台阶。

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

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

• 题目背景其实是斐波拉契数列，是典型的使用“动态规划”解决的问题；
• 注意边界情况，一次跳上 n 个台阶，这单独算一种方法，因此，可以设置起点为 1，这就是下面代码中第 13 行的意思；
• 可以进一步归纳，具体见讨论区相应的解答。

Java 代码：

  public class Solution {
        // 1 2 3
        public int JumpFloorII(int target) {
            if (target == 0 || target == 1) {
                return 1;
            }
            int n = target;
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                // 起点是 1 这一点要特别小心
                int res = 1;
                for (int j = 1; j < i; j++) {
                    res += dp[j];
                }
                dp[i] = res;
            }
            return dp[n];
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int jumpFloorII = solution.JumpFloorII(3);
            System.out.println(jumpFloorII);
        }
    }

Python 代码：因为青蛙一次可以跳任意台阶，我们就让它跳 n 阶，所以初始值设置为 1 。

  class Solution:
        def jumpFloorII(self, number):
            if number == 0:
                return 1
            if number == 1:
                return 1
            dp = [1 for _ in range(number + 1)]
            dp[0] = 0
            dp[1] = 1
            for i in range(2, number + 1):
                for j in range(1, i):
                    dp[i] += dp[j]
            return dp[number]

思路2：

当 n=1 时，结果为 1；

当 n=2 时，结果为 2；

当 n=3 时，结果为 4；

……

以此类推，使用数学归纳法不难发现，跳法 f(n)=2^{n-1}。

Python 代码：

  class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number <= 2:
                return number
            total = 1
            for _ in range(1, number):
                total *= 2
            return total

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/