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

【leetcode刷题】T159-爬楼梯

木又连续日更第19天(19/138)


木又的第159篇leetcode解题报告

动态规划类型第2篇解题报告

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) = 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 < 3:
            return n
        a, b = 1, 1
        for i in range(1, n):
            a, b = b, a+b
        return b

C++版本

class Solution {
public:
    int climbStairs(int n) {
        // 斐波那契数列 f(n) = f(n-1) + f(n-2)
        if(n < 3)
            return n;

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

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

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

原始发表时间:2019-09-03

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】20T34-爬楼梯

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

    木又AI帮
  • 【leetcode刷题】T44-两个数组的交集 II

    Given two arrays, write a function to compute their intersection.

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

    Given an array of integers, find out whether there are two distinct indices i an...

    木又AI帮
  • 51Nod-1443-路径和树

    ACM模版 描述 ? 题解 这个题是单源最短路 + 最小生成树。 首先我们来介绍一下题中所述的最短路径树是什么,我们都知道,给定一个 uu 求单源最短路时,所有...

    f_zyj
  • 2014年第五届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • 强联通模板

    #include<stdio.h> #include<string.h> #include<vector> #include<stack> using name...

    用户1624346
  • 强连通专题

    POJ 2762 Going from u to v or from v to u? 题意:判断该图的任意两点是否可达 分析:tarjan后进行缩点,缩点后再建...

    用户1624346
  • 1464: [蓝桥杯2019初赛]数的分解

    把2019分解成3个各不相同的正整数之和,并且要求每个正整数都不包含数字2和4,一共有多少种不同的分解方法?注意交换3个整数的顺序被视为同一种方法,例如1000...

    可爱见见
  • Remove Duplicates from Sorted Array

    问题:将有序的数组中重复的数字去掉 分析:由于有序所以只用和前一个比较就行 class Solution { public: int removeDup...

    用户1624346
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券