1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3260.html

« [剑指 Offer 第 2 版第 10 题] “矩形覆盖”做题记录
[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录»

相关推荐

QR code