House Robber Solutions in C++

// Source : https://leetcode.com/problems/house-robber/
// Author : Hao Chen
// Date   : 2015-04-07



#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;    
/*
 * Dynamic Programming
 *
 * We can easy find the recurive fomular:
 *
 *     dp[n] = max( 
 *                    dp[n-1],   // the previous house has been robbed. 
 *                    dp[n-2] + money[n]  // the previous house has NOT been robbed.
 *                )
 *                  
 * The initalization is obvious:
 *     dp[1] = money[1]
 *     dp[2] = max(money[1], money[2])
 *
 */
int rob1(vector<int> &money) {

    int n = money.size();
    if (n==0) return 0;

    vector<int> dp(n, 0);
    if (n>=1) dp[0] = money[0];
    if (n>=2) dp[1] = max(money[0], money[1]);

    for (int i=2; i<n; i++){
        dp[i] = max(dp[i-1], dp[i-2] + money[i]);
    }
    return dp[n-1];
}
/*
 * Acutally, we no need to allocate an additional array for DP.
 * we can only use several variables to record previous steps
 */

int rob2(vector<int> &money) {
    int n2=0; // dp[i-2];
    int n1=0; // dp[i-1];

    for (int i=0; i<money.size(); i++){
        int current = max(n1, n2 + money[i]);
        n2 = n1;
        n1 = current;
    }
    return n1;
}

int rob(vector<int> &num) {
    if (rand()%2)
        return rob1(num);
    return rob2(num);
}

void printVector( vector<int> &v ){
    cout << '[' ;
    for(int i=0; i<v.size(); i++){
        cout << v[i] << (i==v.size()-1 ? " " :", ");
    }
    cout << ']' << endl;
}

int main(int argc, char** argv) {
    srand(time(0));
    vector<int> money;
    if (argc>1){
        for (int i=1; i<argc; i++) {
            money.push_back(atoi(argv[i]));
        }
    }else{
        money.push_back(2);
        money.push_back(1);
        money.push_back(3);
        money.push_back(4);
    }

    printVector(money);
    cout << rob(money) << endl;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
private:
    // the max profit for robbing nums[i...n)
    vector<int> memo;

    int tryRob(const vector<int> &nums, int index){

        if(index >= nums.size())
            return 0;

        if(memo[index] != -1)
            return memo[index];

        return memo[index] = max(tryRob(nums, index + 1),
                                 nums[index] + tryRob(nums, index + 2));
    }

public:
    int rob(vector<int>& nums) {

        memo.clear();
        for(int i = 0 ; i < nums.size() ; i ++)
            memo.push_back(-1);
        return tryRob(nums, 0);
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int rob(vector<int>& nums) {

        int n = nums.size();

        if(n == 0)
            return 0;

        // the max profit for robbing nums[i...n)
        vector<int> memo(n, 0);
        memo[n - 1] = nums[n - 1];
        for(int i = n - 2 ; i >= 0 ; i --)
            memo[i] = max(memo[i + 1],
                          nums[i] + (i + 2 < n ? memo[i + 2] : 0));

        return memo[0];
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19
#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming, with O(1) space
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    int rob(vector<int>& nums) {

        int n = nums.size();

        if(n == 0)
            return 0;

        int preMax = 0, curMax = 0;
        for(int i = n - 1 ; i >= 0 ; i --) {
            int temp = curMax;
            curMax = max(curMax, nums[i] + preMax);
            preMax = temp;
        }
        return curMax;
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Memory Search
/// Another way to define the states
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    // the max profit for robbing nums[0...i]
    vector<int> memo;

    int tryRob(const vector<int> &nums, int index){

        if(index < 0)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        return memo[index] = max(tryRob(nums, index - 1),
                                 nums[index] + tryRob(nums, index - 2));
    }

public:
    int rob(vector<int>& nums) {

        memo.clear();
        for(int i = 0 ; i < nums.size() ; i ++)
            memo.push_back(-1);
        return tryRob(nums, nums.size() - 1 );
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Another way to define the states
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int rob(vector<int>& nums) {

        int n = nums.size();
        if( n == 0 )
            return 0;

        // the max profit for robbing nums[0...i]
        vector<int> memo(n, 0);
        memo[0] = nums[0];
        for(int i = 1 ; i < n ; i ++)
            memo[i] = max(memo[i - 1],
                          nums[i] + (i - 2 >= 0 ? memo[i - 2] : 0));

        return memo[n-1];
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming with O(1) space
/// Another way to define the states
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    int rob(vector<int>& nums) {

        int n = nums.size();
        if( n == 0 )
            return 0;

        int curMax = 0, preMax = 0;
        for(int i = 0 ; i < n ; i ++){
            int temp = curMax;
            curMax = max(curMax, nums[i] + preMax);
            preMax = temp;
        }

        return curMax;
    }
};

int main() {

    int nums[] = {2, 1};
    vector<int> vec(nums, nums + sizeof(nums)/sizeof(int));

    cout << Solution().rob(vec) << endl;

    return 0;
}