Leetcode 198. House Robber

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

House Robber

2. Solution

• Version 1

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

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);
    }
};

Reference

1. https://leetcode.com/problems/house-robber/description/