专栏首页后端码事台阶很高,青蛙跳不跳?

台阶很高,青蛙跳不跳?

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

一只青蛙一次可以跳上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;
    }

空间复杂度降为O(1)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode 一些算法题及答案

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    WindWant
  • 基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

    项目地址:https://github.com/windwant/windwant-service/tree/master/algorithm

    WindWant
  • 队列的一种实现:循环队列

    WindWant
  • 漫画:神奇的找出只出现一次的数字!

    第136题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    程序员小浩
  • 程序员进阶之算法练习(三十四)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

    落影
  • 2018年各大互联网前端面试题二(滴滴打车)

    王小婷
  • 【算法精讲】分享一道很不错的算法题

    郑重声明:本文为苦逼的码农原创,未经同意禁止任何形式转载,特别是那些直接复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢

    帅地
  • leetcode Sum 系列----寻找和为定值的多个数

    july 大神有个程序员编程艺术系列,第五章《寻找和为定值的多个数》,现在我们站在大牛的肩膀上,对leetcode上n个数求和的系列问题做个阶段性总结。

    流川疯
  • rsyslog将日志记录于MySQL中并web显示

    咻一咻
  • Single Number

    Tyan

扫码关注云+社区

领取腾讯云代金券