每天进步一点点🤏

爬楼梯

  • 1247 字

爬楼梯

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
思路:
爬楼梯的结果,包含从n-1的楼梯向上爬一步和从n-2的楼梯向上爬两步
f(n) = f(n-1)+f(n-2) 当n=1,返回1,当n=2,返回2
类似斐波那契数列

代码:
function climbStairs($n)
{
    if ($n < 3) {
        return $n;
    }
    $a = 1;
    $b = 2;
    $c = 0;
    for ($i = 1; $i < $n - 1; $i++) {
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }

    return $c;
}

如果使用递归,可能会超时
function climbStairs($n)
{
    if ($n == 1) {
        return 1;
    }

    if ($n == 2) {
        return 2;
    }

    return $this->climbStairs($n - 1) + $this->climbStairs($n - 2);
}

需要加缓存
private $map = [];

function climbStairs($n)
{
    if ($n == 1) {
        return 1;
    }

    if ($n == 2) {
        return 2;
    }

    if (isset($this->map[$n])) {
        return $this->map[$n];
    }

    $data = $this->climbStairs($n - 1) + $this->climbStairs($n - 2);

    $this->map[$n] = $data;

    return $data;
}