題目
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.
思路
這道題的本質相當于在1列數組中取出1個或多個不相鄰數，使其和最大。
這是1道動態計劃問題。
我們保護1個1位數組dp，其中dp[i]表示到i位置時不相鄰數能構成的最大和。
狀態轉移方程：
dp[0] = num[0] （當i=0時）
dp[1] = max(num[0], num[1]) （當i=1時）
dp[i] = max(num[i] + dp[i - 2], dp[i - 1]) （當i !=0 and i != 1時）
代碼
/*-------------------------------------------------------------------
* 日期：2014-04-08
* 作者：SJF0115
* 題目: 198.House Robber
* 來源：https://leetcode.com/problems/house-robber/
* 結果：AC
* 來源：LeetCode
* 總結：
--------------------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int rob(vector<int> &num) {
if(num.empty()){
return 0;
}//if
int size = num.size();
vector<int> dp(size,0);
// dp[i]=max(num[i]+dp[i⑵],dp[i⑴])
// dp[i]表示[0,i]取1個或多個不相鄰數值的最大收益
dp[0] = num[0];
dp[1] = max(num[0],num[1]);
for(int i = 2;i < size;++i){
dp[i] = max(dp[i-1],dp[i-2]+num[i]);
}//for
return dp[size-1];
}
};
int main() {
Solution solution;
vector<int> num = {4,3,1,3,2};
cout<<solution.rob(num)<<endl;
return 0;
}
運行時間
空間優化
用本身數組代替dp數組。
/*-------------------------------------------------------------------
* 日期：2014-04-08
* 作者：SJF0115
* 題目: 198.House Robber
* 來源：https://leetcode.com/problems/house-robber/
* 結果：AC
* 來源：LeetCode
* 總結：
--------------------------------------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int rob(vector<int> &num) {
if(num.empty()){
return 0;
}//if
int size = num.size();
num[1] = max(num[0],num[1]);
for(int i = 2;i < size;++i){
num[i] = max(num[i-1],num[i-2]+num[i]);
}//for
return num[size-1];
}
};
int main() {
Solution solution;
vector<int> num = {4,3,1,3,2};
cout<<solution.rob(num)<<endl;
return 0;
}
運行時間
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
