iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 10
0
Software Development

從LeetCode學演算法系列 第 10

[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

分析/解題:
題目描述有一個要爬n階才能到頂端的階梯,每次只能爬1階或2階,
試求有多少種不同的方法可以走到頂端。
如果以窮舉的話我們可能需要列很久,
所以這時候又回到了看看是否能找出相互關係的時候了。

我們考慮要爬n階的話,首先要先爬到n-1階或n-2階,
因為只有一次走1階或一次走2階的選擇。
也就是說,走到n階的方法,就相當於走到n-1階的方法和走到n-2階的方法和
因為最後的步伐已經固定了,
我們同時還可以保證這兩個方法的組合之間不會互相重複
(一個最後走1步,一個最後走2步)。

我們可以選擇開一個res的陣列,初始化前2階以後,
一路加上去最終得到到第n階的方法數,下面Java的版本因為陣列由0開始,
有刻意將數字不先行化簡,讀者應該可以很簡單地對照。

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來輪替使用,可以節省記憶體。
每次應該要做的,是將s1+s2的值擺到s2,而將s2的值擺到s1的位置。
(等於把兩個數代表的位置遞移了一層)
(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), 依方法而定,
上面Java的寫法需要O(N),Python的寫法則只需O(1))

「哪個寫法比較好?」
(以空間節省的角度來說是Python版本的寫法較佳,
但如果我們不止需要算一次的話,執行一次n階,
其實可以將n階以下的走法數量全部記起來,
這樣被讀取的時候可以先查是否可以直接拿結果回傳,
所以反覆執行的效率會變比較好,不過這個就需要再修改一下程式就是了)

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0083. Remove Duplicates from Sorted List (Easy)


上一篇
[Day 9] 從LeetCode學演算法 - 0067. Add Binary (Easy)
下一篇
[Day 11] 從LeetCode學演算法 - 0083. Remove Duplicates from Sorted List (Easy)
系列文
從LeetCode學演算法30

1 則留言

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

感謝這個系列文的分享
目前從Day1-10的題目都做過一遍了
每一次也都寫下筆記
這段期間真的收穫了很多
也有實際用在工作上
下禮拜我會繼續從Day11開始努力的

我要留言

立即登入留言