0070._climbing_stairs.md

Navigation

• Navigation
• Links:
• Tags
• Solution 1 斐波那契数列
• Solution 2 动态规划

Links:

1. https://leetcode.com/problems/climbing-stairs/
2. https://leetcode-cn.com/problems/climbing-stairs/

Tags

1. 动态规划

Solution 1 斐波那契数列

设爬 n 个台阶有 f(n) 种可能： 假设先爬1阶，剩下 n-1 阶有 f(n-1) 种可能； 假设先爬2阶，剩下 n-2 阶有 f(n-2) 种可能， 所以：f(n) = f(n-1) + f(n-2)； 此题可转化为求斐波那契数列第n项。

class Solution:
    def climbStairs(self, n):
        a, b = 1, 1

        for _ in range(n - 1):  # for i in range(2, n+1):
            a, b = b, a + b

        return b

Go

func climbStairs(n int) int {
	a, b := 1, 1

	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}

	return b
}

Solution 2 动态规划

f(n) = f(n-1) + f(n-2)。可以看作大的问题依赖小的问题的解，所以是动态规划。 状态转移方程：dp[i] = d[i-2] + dp[i-1]。 到达当前楼梯的路径数 = 到达上个楼梯的路径数 + 到达上上个楼梯的路径数。

class Solution:
    def climbStairs(self, n):
        steps = [1, 2]

        for i in range(2, n):
            steps.append(steps[i - 1] + steps[i - 2])

        return steps[n - 1]

---

class Solution(object):
    def climbStairs(self, n):
        steps = [0, 1, 2]
        
        for i in range(3, n+1):
            steps.append(steps[i - 2] + steps[i - 1])
            
        return steps[n]

---

Go

func climbStairs(n int) int {
	steps := []int{1, 2}

	for i := 2; i <= n; i++ {
		steps = append(steps, steps[i-1]+steps[i-2])
	}

	return steps[n-1]
}