70.爬楼梯

题目地址(70. 爬楼梯)

https://leetcode.cn/problems/climbing-stairs/

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

前置知识

• 递归和动态规划

公司

• 暂无

思路

• 动态规则就是要找出状态转移方程

关键点

• f(n) = f(n-1) + f(n-2)，n = 1，f(n)=1；n=2时，f(n)=2

代码

• 语言支持：Java

Java Code:

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        for (int i = 3; i <= n; ++i) {
            int tmp = a;
            a = b;
            b = tmp + b;
        }
        return b;
    }
}

另一种常见写法

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int current = 0;
        int a = 1;
        int b = 2;
        for (int i = 3; i <= n; ++i) {
            current = a + b;
            a = b;
            b = current;
        }
        return current;
    }

Go Code:

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

    a, b, current := 1, 2, 0
    // go没有前置的++i
    for i := 3; i <= n; i++ {
        current = a + b
        a = b
        b = current
    }
    return current
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：
• 空间复杂度：