online advertising

Tuesday, March 31, 2015

LeetCode OJ - House Robber

Problem:

Please find the problem here.

Solution:

A simple application of dynamic programming.
The optimal way to rob all these homes is to either rob the last one and optimally rob the rest without the immediate neighbor, or not rob the last one and optimally rob all the ones before.

In equation, it is

OPT(n) = max(value[n] + OPT(n - 2), OPT(n-1))

With the initial conditions OPT(1) = value[1], and OPT(2) = max(value[1], value[2]).

Be careful with no home, one home or two home only, just special case them.

Could have reduce my memory to just two integers, just didn't bother, either is the judge.

Code:

#include "stdafx.h"

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

#include "LEET_HOUSE_ROBBER.h"
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_HOUSE_ROBBER
{
    class Solution
    {
    public:
        int rob(vector<int> &num)
        {
            if (num.size() == 0)
            {
                return 0;
            }

            vector<int> best;
            best.resize(num.size());
            if (num.size() > 0)
            {
                best[0] = num[0];
            }
            if (num.size() > 1)
            {
                best[1] = max(num[0], num[1]);
            }

            for (unsigned int i = 2; i < num.size(); i++)
            {
                best[i] = max(num[i] + best[i - 2], best[i - 1]);
            }

            return best[num.size() - 1];
        }
    };
};

using namespace _LEET_HOUSE_ROBBER;

int LEET_HOUSE_ROBBER()
{
    Solution solution;
    vector<int> data;
    data.push_back(2);
    data.push_back(1);
    data.push_back(3);
    data.push_back(4);
    cout << solution.rob(data) << endl;
    return 0;
}

1 comment :