leetcode-198

发表于 | 分类于 | 阅读次数:
字数统计: 127 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        last, now = 0, 0
        for i in nums: 
            last, now = now, max(last + i, now)
        return now

采用java做的一版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public static int[] result;
    
    public int solve(int idx, int[] nums){
        if(idx < 0){
            return 0;
        }
        if(result[idx] >= 0){
            return result[idx];
        }
        result[idx] = Math.max(nums[idx]+solve(idx-2, nums), solve(idx-1, nums));
        return result[idx];
    }
    public int rob(int[] nums) {
        result = new int[nums.length];
        for(int i=0;i<nums.length;++i){
            result[i] = -1;
        }
        return solve(nums.length-1, nums);
    }
}