創作內容

1 GP

LeetCode - 70. Climbing Stairs 解題心得

作者:Not In My Back Yard│2020-08-09 00:00:12│巴幣:2│人氣:138
題目連結:


題目意譯:
你正在爬樓梯。需要爬 n 階才會到頂。

每次你可以爬 1 階或 2 階。你會有多少相異的走法可以爬到頂?

限制:
1 ≦ n ≦ 45



範例測資:
範例 1:
輸入: 2
輸出: 2
解釋: 有兩個方法爬到頂。
1. 爬 1 階 + 爬 1 階
2. 爬 2 階

範例 2:
輸入: 3
輸出: 3
解釋: 有三個方法爬到頂。
1. 爬 1 階 + 爬 1 階 + 爬 1 階
2. 爬 1 階 + 爬 2 階
3. 爬 2 階 + 爬 1 階


解題思維:
可以看到 n = 1 、 2 、 3 、 4 、 5 、 …… 時,方法數為 1 、 2 、 3 、 5 、 8 、 ……,而此即為費氏數列。

因為當要求 n = k 的方法數時,可以來到第 k 階的,可能是從第 k - 1 階走一階上來或是從第 k - 2 階走兩階上來。也就是方法數 = k - 1 的方法數 + k - 2 的方法數。此即為費氏數列的遞迴關係式。除了階梯走法是以 1 、 2 開頭,費氏則是以 1 、 1 開頭。兩者差了一個「1」,但其後完全一致。

因此,我們可以用三個變數 F 、 S 以及一個暫存用的變數 buffer(F 、 S 初始化為 1 、 1)。接著做 n 次以下的步驟:
將 F + S 之值存進 buffer 裡,然後將 F 之值更新成 S 之值,最後將 S 之值更新為 buffer 之值。
上述做完 n 次之後即可得到所求的走 n 階階梯之方法數。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4876415
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|模擬

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

1喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

tfapp大家
最近待在家是最好的選擇,小屋內容新增,歡迎大家到我的小屋,免費以及輕鬆愉快學日文看更多我要大聲說昨天17:16


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】