专栏首页木又AI帮【leetcode刷题】20T34-爬楼梯

【leetcode刷题】20T34-爬楼梯


木又同学2020年第34篇解题报告

leetcode第70题:爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/


【题目】

假设你正在爬楼梯。需要 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 阶

【思路】

使用f(n)代表爬n阶楼梯的方法数量,我们考虑最后一步,有两种可能:从n-2阶楼梯爬上去,那么有爬到n-2阶楼梯有f(n-2)种方法;从n-1阶楼梯爬上去,爬到n-1阶楼梯有f(n-1)种方法。那么总共有f(n-1) + f(n-2)种方法。

即:f(n) = f(n-1) + f(n-2)。

想想,这是什么公式?

斐波那契数列。

【代码】

python版本

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # f(n) = f(n-1) + f(n-2)
        if n <= 2:
            return n
        a, b = 2, 1
        for i in range(2, n):
            a, b = a + b, a
        return a

C++版本

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2)
            return n;

        // f(n) = f(n-1) + f(n-2)
        int a = 2, b = 1, tmp = 0;
        for (int i = 2; i < n; i++) {
            tmp = a;
            a = a + b;
            b = tmp;
        }
        return a;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • 打卡群刷题总结0626——括号生成

    链接:https://leetcode-cn.com/problems/generate-parentheses

    木又AI帮
  • 【leetcode刷题】T36-存在重复元素

    Given an array of integers, find if the array contains any duplicates.

    木又AI帮
  • 骰子作画

    xiaohejun
  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • hihoCoder 1700 相似颜色

            题目链接: http://hihocoder.com/problemset/problem/1700

    Ch_Zaqdt
  • BZOJ 3932: [CQOI2015]任务查询系统(主席树)

    attack
  • Android实现类似QQ对话框的@他人的整体解决方案

    在我们公司的新版APP中社区板块有个在回复回帖中有个@他们的功能,基本需求和QQ群组对话框里@群或组里任何一个成员类似。而数据传输方面,选择了直接传输富文本格式...

    1025645
  • 【USACO 3.2】Sweet Butter(最短路)

    枚举到的某点,然后优先队列优化的dijkstra求最短路,把给定的点到其的最短路加起来,更新最小值。复杂度是

    饶文津
  • BUPT2017 wintertraining(15) #1 题解

    求逆元。以前写过题解,http://www.cnblogs.com/flipped/p/5193777.html

    饶文津

扫码关注云+社区

领取腾讯云代金券