An easy-understanding solution in C++

  • 6

    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 {
        int rob(vector<int> &nums) {
            if (nums.size() == 0) {
                return 0;
            if (nums.size() == 1) {
            vector<int> case1(nums);
            vector<int> case2(nums);
            vector<int>::iterator v1 = case1.begin();
            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] =;
                else {
                    f[i] = max(f[i-2] +, 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.