专栏首页Android先生简单动态规划—爬楼梯

简单动态规划—爬楼梯

又到了每周的算法时间了,今天给大家带来一道很经典,又很简单,又比较适合对动态规划极度恐惧的童鞋,做动态规划的题,一定要学会分析,慢慢找到状态转移方程,不多说,来看看题目:

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入:2
输出:2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入:3
输出:3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解题思路

这道题目算得上最简单的动态规划类的题目了,我们来一个一个分析一下:

  • 当只有 1 阶台阶时,你只有一种方式爬到顶端
  • 当只有 2 阶台阶时,你有两种方式,如示例1所示
  • 当只有 3 阶台阶时,你有三种方式,如示例2所示

分析到这里的时候,看看这几个数据,我有一个大胆的猜测,当只有 4 阶台阶时,可以有 爬到第2阶台阶所需要的方法数 加上 爬到第3阶台阶所需要的方法数 种方法数,为什么这么说呢?你想想,要想爬到第4阶台阶,你只能是从第3阶或者第2阶台阶爬上来的,只有这两种方式对吧,所以:

4阶方法总数 = 3阶方法总数 + 2阶方法总数

WX20200305-203423@2x.png

题解

public static int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int[] steps = new int[n];
    steps[0] = 1;
    steps[1] = 2;
    for (int i = 2; i < n; i++) {
        steps[i] = steps[i - 1] + steps[i - 2];
    }
    return steps[n - 1];
}

本文分享自微信公众号 - IT先森养成记(cyg_24kshign),作者:24K纯帅豆

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

原始发表时间:2020-03-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RecyclerView 梳理:点击&amp;长按事件、分割线、拖曳排序、滑动删除

    这次主要是把 RecyclerView 比较常用的基本的点,在这里集中整理一下。从这篇文章主要梳理以下几点:

    用户2802329
  • RecyclerView 自定义ItemDecoration从入门到实现吸顶效果

    RecyclerView性能和自由度相比ListView强大很多,但很恼人的是它没有像ListView一样默认提供分割线。

    用户2802329
  • Gradle从入门到了解 - 简书

    Gradle(英[g'reɪdl])是一个任务驱动型的构建工具,是一个依赖管理工具,更是一个编程框架。 它抛弃了基于XML的各种繁琐配置,取而代...

    用户2802329
  • R代码|dplyr包的使用示例

    代码来自《r-data-science-quick-reference-master》的内容。

    生信交流平台
  • 秒杀架构实践

    之前在 Java-Interview 中提到过秒杀架构的设计,这次基于其中的理论简单实现了一下。

    纯洁的微笑
  • 手把手带你秒杀架构实践(含完整代码)

    之前在 Java-Interview 中提到过秒杀架构的设计,这次基于其中的理论简单实现了一下。

    java进阶架构师
  • vue自定义transition样式前缀名

    默认情况下,控制 transition 样式的类名是以 'v-' 为前缀,我们可以自定义前缀名

    章鱼喵
  • Mathematica 11在概率和统计方面的新功能

    WolframChina
  • 2018年技术预测:五大危机还是五大机遇?

    预测就像是公共巴士,要么没人来,要么就好几个人一起来。不仅如此,它们比你想的要来的慢,而且只是把你带到了路边。它们还非常热闹,充满了你早上通勤时不想听见的种种喋...

    全球资讯翻译官
  • 制作HackCube中的坎坎坷坷

    由于自己对于无线电方面的信息安全的热爱。在中秋放假之前自己按照360无线电无线电研究院的帖子DIY了一个hack cube。这个hack cube我只使用了其中...

    FB客服

扫码关注云+社区

领取腾讯云代金券