leetcode-php/src/leetcode/ClimbingStairs.php at master · imajinyun/leetcode-php · GitHub

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
<?php

declare(strict_types=1);

namespace leetcode;

class ClimbingStairs
{
    public static function climbStairs(int $n): int
    {
        if ($n <= 0) {
            return 0;
        }
        if ($n === 1 || $n === 2) {
            return $n;
        }

        $dp = [1 => 1, 2 => 2];
        for ($i = 3; $i <= $n; $i++) {
            $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
        }

        return $dp[$n];
    }

    public static function climbStairs2(int $n): int
    {
        if ($n <= 0) {
            return $n;
        }
        if ($n === 1 || $n === 2) {
            return $n;
        }
        [$prev, $curr] = [1, 1];
        for ($i = 2; $i < $n + 1; $i++) {
            $temp = $curr;
            $curr = $prev + $curr;
            $prev = $temp;
        }

        return $curr;
    }
}