LeetCode，Go 實現爬樓梯算法
力扣題目：
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
LeetCode 題目源地址：https://leetcode-cn.com/problems/climbing-stairs/
解題思路
我們先列舉幾個例子：
-
假設有 1 級臺階，則有 1 種方法
-
爬 1 級
-
假設有 2 級臺階，則有 2 種方法
-
爬 1 級
-
爬 2 級
-
假設有 3 級臺階，則有 3 種方法
-
分別爬 1 級
-
先爬 1 級 再爬 2 級
-
先爬 2 級 再爬 1 級
可見, 如果有 n 級臺階，那麼方法就是前兩級臺階的方法之和，即 (n-1) + (n-2)
程序實現
- 遞歸
首先想到的方法就是遞歸了
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n==2{
return 2
}
return climbStairs(n-1) + climbStairs(n-2)
}- 動態規劃方法：
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n==2{
return 2
}
a := 1
b := 2
for i:= 3; i <= n; i++{
temp := a
a = b
b = temp + a
}
return b
}有什麼問題，可以公衆號內回覆或加我微信交流。
微信公衆號
gophpython
我的微信
wucs_dd
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/FYVHHzAx_3Ov9BY2vSuTIA