DAY 10
0
Software Development

## [Day 10] 從LeetCode學演算法 - 0070. Climbing Stairs (Easy)

``````Question:
You are climbing a staircase. 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
``````

(一個最後走1步，一個最後走2步)。

Java:

``````class Solution {
public int climbStairs(int n) {
if(n <= 2) return n;
int[] res = new int[n];
res[1-1] = 1;
res[2-1] = 2;
for(int i = 3; i <= n; i++) {
res[i-1] = res[i-1-1] + res[i-2-1];
}
return res[n-1];
}
}
``````

Python的部分，則採用兩個數s1, s2來輪替使用，可以節省記憶體。

(等於把兩個數代表的位置遞移了一層)
(Java也可以用類似的作法，但需要多宣告一個暫存值進行儲存)

Python:

``````class Solution:
def climbStairs(self, n: 'int') -> 'int':
if n == 1:
return 1
if n == 2:
return 2
s1, s2 = 1, 2
for _ in range(n - 2):
s1, s2 = s2, s1 + s2
return s2
``````

「時間/空間複雜度？」
（O(N), 依方法而定，

「哪個寫法比較好？」
(以空間節省的角度來說是Python版本的寫法較佳，

0083. Remove Duplicates from Sorted List (Easy)

### 1 則留言

0
t19960804
iT邦新手 5 級 ‧ 2020-08-16 17:08:18