分治01--跳台階

分治01--跳台階-jz08

• ​​題目概述​​
• ​​解析&參考答案​​
• ​​注意事項​​
• ​​說明​​

題目概述

• 算法說明

  一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。

• 測試用例

  輸入： 3

  輸出： 3

解析&參考答案

• 解析

  最簡單的方式使用遞歸，總跳法為 jumpFloor(number-1) + jumpFloor(number-2)；

• 參考答案

vim jz08.go
package main

import "fmt"

func jumpFloorV2(number int) int {
    if number <= 1 {
        return 1
    }
    a, b, c := 1, 1, 0
    for i := 2; i <= number; i++ {
        c = a + b
        a = b
        b = c
    }
    return c
}

func jumpFloor(number int) int {
    if number <= 1 {
        return 1
    }
    return jumpFloor(number-1) + jumpFloor(number-2)
}

func main() {
    n := 3
    result := jumpFloorV2(n)
    fmt.Println(result)
}      

注意事項

1. 實際中最好将遞歸更改為循環，進而提高效率；

說明

1. 目前使用 go1.15.8
2. 參考​​牛客網--劍指offer​​ 标題中jzn(n為具體數字)代表牛客網劍指offer系列第n号題目，例如 jz01 代表牛客網劍指offer中01号題目。

• 筆者最近在學習 golang，是以趁機通過資料結構和算法來進一步熟悉下go語言
• 目前算法主要來源于劍指 offer，後續會進一步補充 LeetCode 上重要算法，以及一些經典算法
• 此處答案僅為參考，不一定是最優解，歡迎感興趣的讀者在評論區提供更優解