题目链接
https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/
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 step + 1 step
- 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
解题思路
到第n个台阶有两个情况：
- 在第n - 1个台阶，迈一个台阶过去
- 在第n - 2个台阶，迈两个台阶过去
可以推断出：F(n) = F(n - 1) + F(n - 2)
方法一：直接使用递归，验证结果超时
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
方法二：不使用递归方法
初始化一个N长度的数组，并全部初始化为1，从第2个元素（0开始计数）开始使用F(n) = F(n - 1) + F(n - 2)计算每个台阶的step数
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1 for i in range(n + 1)]
for i in range(2, 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
"""
if n == 1:
return 1
if n == 2:
return 2
first = 1
second = 2
res = 0
for i in range(3, n + 1):
res = first + second
first = second
second = res
return res
