Golang | Leetcode Golang题解之第70题爬楼梯

题目描述：

一只青蛙一次可以跳上台阶的一级或两级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解法1：递归

在这个问题中，我们可以使用一种自上而下的策略，这就需要我们定义一个递归函数。这个递归函数接收一个参数n，表示台阶的数量。如果n等于0，那么就应该返回0，因为在0级台阶上不能进行任何跳法。如果n等于1，那么就只有一种跳法，返回1。如果n等于2，那么有两种跳法，返回2。否则，就有两种选择，要么跳一级，要么跳两级，所以我们的结果是跳一级的情况的结果加上跳两级的情况的结果。

func climbStairs(n int) int {
    if n <= 1 {
        return n
    }
    return climbStairs(n-1) + climbStairs(n-2)
}

解法2：动态规划

虽然递归解法很直观，但是它效率很低，因为有很多重复的计算。我们可以使用一个数组来保存中间结果，这样就可以避免重复计算。

func climbStairs(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

解法3：线性动态规划

我们还可以进一步优化空间复杂度，使用线性的动态规划。

func climbStairs(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 1, 2
    for i := 2; i < n; i++ {
        a, b = b, a+b
    }
    return b
}

以上就是三种解法，分别是递归，动态规划，和线性动态规划。递归的方法效率很低，动态规划和线性动态规划的方法效率较高。