198. 打家劫舍

1
impl Solution {
2
    pub fn rob(nums: Vec<i32>) -> i32 {
3
        // f(1) = nums[0]
4
        // f(2) = max(nums[0], nums[1])
5
        // f(3) = max(f(1) + nums[2], f(2))
6
        // f(4) = max(f(2) + nums[4], f(3))
7
        // f(n) = max(f(n-2) + nums[n], f(n-1))
8
        //
9
        // example1
10
        // f(1) = 1
11
        // f(2) = max(1, 2) = 2
12
        // f(3) = max(1 + 3, 2) = 4
13
        // f(4) = max(2 + 1, 4) = 4
14
        //
15
        // example2
16
        // f(1) = 2
17
        // f(2) = 7
18
        // f(3) = max(2 + 9, 2) = 11
19
        // f(4) = max(3 + 7, 11) = 11
20
        // f(5) = max(1 + 11, 11) = 12
21

22
        if nums.len() == 1 {
23
            return nums[0];
24
        }
25

26
        let mut arr = vec![0; nums.len()];
27
        arr[0] = nums[0];
28
        arr[1] = nums[0].max(nums[1]);
29

30
        for i in 2..nums.len() {
31
            let a = arr[i-2] + nums[i];
32
            let b = arr[i-1];
33
            arr[i] = a.max(b);
34
        }
35

36
        arr[arr.len() - 1]
37
    }
38
}

1
impl Solution {
2
    pub fn rob(nums: Vec<i32>) -> i32 {
3
        // f(1) = nums[0]
4
        // f(2) = max(nums[0], nums[1])
5
        // f(3) = max(f(1) + nums[2], f(2))
6
        // f(4) = max(f(2) + nums[4], f(3))
7
        // f(n) = max(f(n-2) + nums[n], f(n-1))
8
        //
9
        // example1
10
        // f(1) = 1
11
        // f(2) = max(1, 2) = 2
12
        // f(3) = max(1 + 3, 2) = 4
13
        // f(4) = max(2 + 1, 4) = 4
14
        //
15
        // example2
16
        // f(1) = 2
17
        // f(2) = 7
18
        // f(3) = max(2 + 9, 2) = 11
19
        // f(4) = max(3 + 7, 11) = 11
20
        // f(5) = max(1 + 11, 11) = 12
21

22
        if nums.len() == 1 {
23
            return nums[0];
24
        }
25

26
        let mut states = vec![
27
            nums[0],
28
            nums[0].max(nums[1]),
29
        ];
30
        let mut index = 0;
31

32
        for i in 2..nums.len() {
33
            states[index] = if index == 0 {
34
                let a = states[0] + nums[i];
35
                let b = states[1];
36
                a.max(b)
37
            } else {
38
                let a = states[1] + nums[i];
39
                let b = states[0];
40
                a.max(b)
41
            };
42

43
            index = if index == 0 {
44
                1
45
            } else {
46
                0
47
            };
48
        }
49

50
        states[if index == 0 {
51
            1
52
        } else {
53
            0
54
        }]
55
    }
56
}