|
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 1.递归,用递归超时
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n-1) + self.climbStairs(n-2)
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 2.记忆化递归
memory = [0 for i in range(n+1)]
return self.climbStairsMemory(n, memory)
def climbStairsMemory(self, n, memory):
if memory[n] > 0:
return memory[n]
if n == 1:
memory[1] = 1
elif n == 2:
memory[2] = 2
else:
memory[n] = self.climbStairsMemory(n-1,memory) + self.climbStairsMemory(n-2,memory)
return memory[n]
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 3.动态规划
# 没有这个if判断，当输入n=1时，dp[2]=2超出下标范围
if n == 1:
return 1
dp = [0 for i in range(n+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]
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 4.动态规划+滚动数组
if n == 1:
return 1
first = 1
second = 2
for _ in range(3,n+1):
result = first + second
first = second
second = result
return second
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 5.动态规划+滚动数组
p = q = 0
r = 1
for i in range(1,n+1):
p = q
q = r
r = p + q
return r
| 
