专栏首页小浩算法《剑指offer》第十天:青蛙跳台阶

《剑指offer》第十天:青蛙跳台阶

小白写的代码:

老司机写的代码:

跳台阶

题目描述

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

相关阅读

之前我写过的爬楼梯,和本题类似:

DP:爬楼梯

当然,也可以看我写过的完整动态规划系列:

动态规划入门看这篇就够了,万字长文!

解法

跳上 n 级台阶,可以从 n-1 级跳 1 级上去,也可以从 n-2 级跳 2 级上去。所以

f(n) = f(n-1) + f(n-2)
public class Solution {
    /**
     * 青蛙跳台阶
     * @param target 跳上的那一级台阶
     * @return 多少种跳法
     */
    public int JumpFloor(int target) {
        if (target < 3) {
            return target;
        }
        int[] res = new int[target + 1];
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= target; ++i) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[target];
    }
}

测试用例

  1. 功能测试(如输入 3、5、10 等);
  2. 边界值测试(如输入 0、1、2);
  3. 性能测试(输入较大的数字,如 40、50、100 等)。

内容展示:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-14

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字节尿性,康托展开求第K个排列!

    那康托展开是干嘛的?用来计算当前排列在所有由小到大全排列中的顺序。卧槽,不就是本题吗。

    程序员小浩
  • 面试超级爱问的全排列!!!

    假如我们不是做算法题,而是做数学题。我们会一个位置一个位置的来考虑,先写出以1开头的排列,再写出以2开头的排列,最后写出以3开头的排列。

    程序员小浩
  • 漫画:滑动窗口入门题目,没有之一

    今天是小浩算法“365刷题计划”第83天 。昨天写了一篇感悟,没想到那么受欢迎。几百人转发,好几千人阅读,虚荣心得到了极大的满足。今天继续为大家分享一道经典面试...

    程序员小浩
  • 一文弄懂数组的和

    方法二:对于第一种方法,主要时间都用在进行排序上,我们可以利用hash来避免进行排序。

    绝命生
  • 可穿戴设备技术方案

    室内定位能力排行旁:蓝牙、wifi、gprs、gps(除非室内自建gps路由器,前期投入巨大)

    用户2188327
  • elasticsearch实战三部曲之一:索引操作

    从本章开始,我们一起来实战elasticsearch,熟悉相关操作和命令,为后续的深入学习打好基础;

    程序员欣宸
  • 浅析.NET的反射特性

         在.net框架体系内,反射特性较多的应用到。反射的相关定义分为两种。     自然解释:射是一种自然现象,表现为受刺激物对刺激物的逆反应;这...

    彭泽0902
  • Java对象初始化顺序

    最近我发现了一个有趣的问题,这个问题的答案乍一看下骗过了我的眼睛。看一下这三个类:

    哲洛不闹
  • Android训练课程(Android Training) - 高效的显示图片

    了解如何使用通用的技术来处理和读取位图对象,让您的用户界面(UI)组件是可响应的,并避免超过你的应用程序内存限制的方式。如果你不小心,位图可以快速消耗可用的内存...

    zhangyunfeiVir
  • useList 列表hook

    可以看到这里设置了三类 query, quryCache 用户重置参数, query 用于更新视图, currentQuery 用于获取最新参数. 这样设...

    copy_left

扫码关注云+社区

领取腾讯云代金券