程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 213:House Robber II

LeetCode 213:House Robber II

編輯:C++入門知識

LeetCode 213:House Robber II


Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

 

//和上一題類似,只是多了一個“環”的條件,就是搶了第一家,就不能搶最後一家
//分別計算搶第二家到最後一家與搶第一家到倒數第二家的最大值,取兩個值中更大的那個就是結果。
class Solution {
public:
	int rob(vector& nums) {
		int n = nums.size();
		if (n == 0) return 0;
		if (n == 1) return nums[0];

		int* dp = new int[n + 1];
		//搶第一家到倒數第二家得到的金錢最大值
		dp[0] = nums[0];  
		for (int i = 1; i < n-1 ; ++i){
			dp[i] = max(dp[i - 1],  (i==1? 0: dp[i-2])+nums[i] );
		}
		int res1=dp[n-2];

		//搶第二家到最後一家得到的金錢最大值
		dp[1] = nums[1];
		for (int i = 2; i < n ; ++i){
			dp[i] = max(dp[i - 1], (i == 2 ? 0 : dp[i - 2]) + nums[i]);
		}
		int res2 = dp[n-1 ];

		return max(res1, res2);//返回二者的較大值
	}
};

\

 

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