leetcode-lintcode/198_house_robber.java at master · lt616/leetcode-lintcode · 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
/* Solution 01: Normal rotating array */
class Solution {
    int[] dpArray;
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        this.dpArray = new int[nums.length + 1];
        this.dpArray[0] = 0;
        this.dpArray[1] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            this.dpArray[i + 1] = Math.max(this.dpArray[i - 1] + nums[i], this.dpArray[i]);
        }

        return this.dpArray[nums.length];
    }
}

/* Solution 02: Reduced memory rotatin array */
class Solution {
    int[] dpArray;
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;

        this.dpArray = new int[2];
        this.dpArray[0] = 0;
        this.dpArray[1] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            this.dpArray[(i + 1) % 2] = Math.max(this.dpArray[(i - 1) % 2] + nums[i], this.dpArray[i % 2]);
        }

        return this.dpArray[nums.length % 2];
    }
}