Q70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:
Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
解题思路:

此题通过观察 n=2, 3, 4, ... 等步数的规律,发现是一个菲波那切数列,即 f(n) = f(n-1) + f(n-2),递归求解即可。

这里没有使用递归,采用动态规划的思想,只保留前两个状态。

Python实现:
# 动态规划
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        one = 0; two = 0;  # 保留前两个状态
        step = 1
        while n > 0:
            one = two
            two = step
            step = one + two
            n -= 1
        return step

a = 3
b = Solution()
print(b.climbStairs(5)) # 8 # f(5) = f(4) + f(3)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3315
来自专栏章鱼的慢慢技术路

解密回文——栈

1513
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

7296
来自专栏数据结构与算法

BZOJ 1174: [Balkan2007]Toponyms

Description 给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. Input 第一行给出...

3006
来自专栏python读书笔记

《算法图解》note 6 图以及广度优先搜索和深度优先搜索1.图2.广度优先搜索3.深度优先搜索

2843
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3515
来自专栏来自地球男人的部落格

[LeetCode] 74. Search a 2D Matrix

【原题】 Write an efficient algorithm that searches for a value in an m x n matrix. ...

1988
来自专栏算法修养

CodeForces 19D Points (线段树+set)

D. Points time limit per test 2 seconds memory limit per test 256 megabyte...

3699
来自专栏云霄雨霁

有向图----有向环检测和拓扑排序

2241
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串,贪心+排序】

Balala Power! Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131...

2875

扫码关注云+社区

领取腾讯云代金券