198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

198. Ограбление домов

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет совершено автоматическое обращение в полицию, если два соседние дома были ограблены в один и тот же вечер. Зная количество денег в каждом доме (задан списком неотрицательных целых чисел), определить максимальную сумму, которую Вы можете ограбить сегодня вечером без обращения в полицию.

// C++

class Solution {

public:

int rob(vector<int>& nums) {

}

};

// Java

public class Solution {

public int rob(int[] nums) {

}

}

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Заведем массив res такой же длины как и num, где res[i] равно наибольшему количеству денег, которое можно получить, ограбив дома с 0-го до i-го. Очевидно, что

res[0] = num[0]

res[1] = max (num[0], num[1])

Пусть вычисляется значение res[i]. Если i-ый дом будет ограблен, то сумма прибыли составит res[i-2] + num[i]. Если i-ый дом не будет ограблен, то прибыль равна сумме, полученной с i-1 дома, то есть res[i-1]. Откуда

res[i] = max(num[i] + res[i - 2], res[i - 1])

Реализация алгоритма

class Solution

{

public:

int rob(vector<int> &num)

{

int sz = num.size();

if (sz == 0) return 0;

vector<int> res(num.size());

if (sz > 0) res[0] = num[0];

if (sz > 1) res[1] = max(num[0],num[1]);

for(int i = 2; i < sz; i++)

res[i] = max(num[i] + res[i - 2], res[i - 1]);

return res[sz - 1];

}

};

Java реализация

public class Solution

{

public int rob(int[] nums)

{

int sz = nums.length;

if (sz == 0) return 0;

int res[] = new int[sz];

if (sz > 0) res[0] = nums[0];

if (sz > 1) res[1] = Math.max(nums[0],nums[1]);

for(int i = 2; i < sz; i++)

res[i] = Math.max(nums[i] + res[i - 2], res[i - 1]);

return res[sz - 1];

}

}