An easy-understanding solution in C++


  • 6
    C

    This problem is an advanced version of Problem "House Robber", the only difference is that the houses are arranged in a circle, which means the first house is adjacent to the last house.

    From a global view, any rob solution has two possible cases: rob the first house, or not.

    If we rob the first house, we can't rob the last house, so the problem transfer to "how to rob in house[1, n-1]". If we do not rob the first house, the problem transfer to "how to rob in house[2, n]".

    Assuming that we have understand the solution for problem "House Robber", now we can simply design the new strategy as below:

    class Solution {
    public:
        int rob(vector<int> &nums) {
            if (nums.size() == 0) {
                return 0;
            }
            if (nums.size() == 1) {
                return nums.at(0);
            }
            vector<int> case1(nums);
            vector<int> case2(nums);
        
            vector<int>::iterator v1 = case1.begin();
            case1.erase(v1);
            case2.pop_back();
        
            int maxRobValue1 = simpleRob(case1);
            int maxRobValue2 = simpleRob(case2);
            int maxRobValue = max(maxRobValue1, maxRobValue2);
            return maxRobValue;
        }
        int simpleRob(vector<int> &num){
            int *f = new int[num.size() + 1];
            f[0] = 0;
            for (int i = 1; i <= num.size(); i++) {
                if (i == 1) {
                    f[i] = num.at(i-1);
                }
                else {
                    f[i] = max(f[i-2] + num.at(i-1), f[i-1]);
                }
            }
            int robMaxValue = f[num.size()];
            return robMaxValue;
        }    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.