70. 爬楼梯 | Yesterday17's Blog

好久没做 DP 了，基本思路就是记录之前状态，然后通过之前的状态推导得出下一个状态的方程（状态转移方程）。

1
impl Solution {
2
    pub fn climb_stairs(n: i32) -> i32 {
3
        // 1 1
4
        // 2
5
        // f(2) = 2
6
        //
7
        // 1 1 1
8
        // 1 2
9
        // 2 1
10
        // f(3) = 2 * f(1) + 1
11
        //
12
        // 1 1 1 1
13
        // 1 1 2
14
        // 1 2 1
15
        // 2 1 1
16
        // 2 2
17
        // f(4) = f(3) + f(2);
18
        //
19
        // f(5) = f(4) + f(3);
20
        //
21
        // f(n) = 1 f(n-1)
22
        //        2 f(n-2)
23

24
        if n == 1 {
25
            return 1;
26
        } else if n == 2 {
27
            return 2;
28
        }
29

30
        let mut data = vec![1, 2];
31
        let mut next = 0;
32

33
        let mut i = 2;
34
        while i < n {
35
            data[next] = data[0] + data[1];
36
            i += 1;
37
            if i == n {
38
                return data[next];
39
            }
40

41
            if next == 0 {
42
                next = 1;
43
            } else {
44
                next = 0;
45
            }
46
        }
47
        data[next]
48
    }
49
}