程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 198 House Robber(強盜盜竊最大值)(動態規劃)(*)

LeetCode 198 House Robber(強盜盜竊最大值)(動態規劃)(*)

編輯:C++入門知識

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);
}
};

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved