[Leetcode][python]Climbing Stairs/爬楼梯
[Leetcode][python]Climbing Stairs/爬楼梯
蛮三刀酱
发布于 2019-03-26 16:20:58
发布于 2019-03-26 16:20:58
题目大意
一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。
解题思路
动态规划，状态转移方程式：
dp[i] = dp[i-1]+dp[i-2]代码
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2:
return n
dp = [1 for __ in range(n)] # 1,2,3,5,8
dp[1] = 2
for i in range(2, n):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]总结
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录