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```

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)```

161 篇文章42 人订阅

0 条评论

相关文章

3315

1513

7296

BZOJ 1174: [Balkan2007]Toponyms

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

3006

2843

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