House Robber

1. Description

2. Solution

• Version 1

代码语言：javascript复制

class Solution {
public:
    int rob(vector<int>& nums) {
    	int n = nums.size();
    	if(n == 0) {
    		return 0;
    	}
        vector<int> maximum(nums.size());
        for(int i = 0; i < n; i  ) {
        	rob(nums, maximum, i);
        }
        return maximum[n - 1];
    }

private:
	void rob(vector<int>& nums, vector<int>& maximum, int current) {
		if(current == 0) {
			maximum[0] = nums[0];
		}
		else if(current == 1) {
			maximum[1] = max(nums[0], nums[1]);
		}
		else {
			maximum[current] = max(maximum[current - 2]   nums[current], maximum[current - 1]);
		}
	}
};

• Version 2

代码语言：javascript复制

class Solution {
public:
    int rob(vector<int>& nums) {
    	int n = nums.size();
    	if(n == 0) {
    		return 0;
    	}
        vector<int> maximum(nums.size());
        rob(nums, maximum, 0);
        return maximum[n - 1];
    }

private:
	void rob(vector<int>& nums, vector<int>& maximum, int current) {
		int n = nums.size();
		if(current == n) {
			return;
		}
		if(current == 0) {
			maximum[0] = nums[0];
		}
		else if(current == 1) {
			maximum[1] = max(nums[0], nums[1]);
		}
		else {
			maximum[current] = max(maximum[current - 2]   nums[current], maximum[current - 1]);
		}
		rob(nums, maximum, current   1);
	}
};

version

0 人点赞