LeetCode 198 House Robber（強盜盜竊最大值）（動態規劃）（*）

LeetCode 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.

分析

典型的動態規劃問題。

int robIter(vector& money, int c, int dp1, int dp2) {
    if (c >= money.size()) return dp2;
    else return robIter(money, c, dp2, max(dp1 + money[c++], dp2));
}

int rob(vector& nums) {
    return robIter(nums, 0, 0, 0);
}

上面寫的可能太簡潔，這樣或許方面理解一些：

int robIter(vector& money, int c, int dp1, int dp2) {
    if (c >= money.size())
        return dp2;
    else {
        dp1 = max(dp1 + money[c++], dp2);
        return robIter(money, c, dp2, dp1);
    }
}

int rob(vector& nums) {
    return robIter(nums, 0, 0, 0);
}

代碼

class Solution {
public:
int robIter(vector& money, int c, int dp1, int dp2) {
    if (c >= money.size()) return dp2;
    else return robIter(money, c, dp2, max(dp1 + money[c++], dp2));
}

int rob(vector& nums) {
    return robIter(nums, 0, 0, 0);
}
};