leetcode 70. 爬楼梯 动态规划 自下而上
发布于2020-04-03 08:56 阅读(1885) 评论(0) 点赞(29) 收藏(3)
人人为我递推型动规
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例 1：输入： 2。输出： 2。解释： 有两种方法可以爬到楼顶。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
思路： 人人为我递推型动规。时间复杂度 O(n)，空间复杂度O(n)。
代码：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp=[0]*(n+1) #dp[i]代表爬到第i阶的方法
if n==1:
return 1
dp[1]=1
dp[2]=2
for i in range(3,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
本博客为原创作品，欢迎指导,转载请说明出处，附上本文链接，谢谢！
原文链接:https://blog.csdn.net/weixin_43973433/article/details/105267157
所属网站分类: 技术文章 > 博客
作者：飞龙出海
链接：https://www.pythonheidong.com/blog/article/301517/17f5ca77083cf4d78580/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力