198. House Robber

為和政等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及和政網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都做網(wǎng)站、成都網(wǎng)站制作、和政網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

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.

解題思路：

房間一共有N個，先判斷到目前為止，前i個房間能獲得最多的金錢。

典型的動態(tài)規(guī)劃。

其中轉(zhuǎn)移方程如下：

maxV[i] = max( maxV[i - 2] + a[i],maxV[i-1]);

其中數(shù)組a[i]為第i個房間隱藏的金錢。maxV[i]表示前i個房間能獲得的最多的錢。

代碼如下：

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        //處理特殊情況
    	if (nums.empty())
    		return 0;
    	if (nums.size() == 1)
    		return nums[0];
    	if (nums.size() == 2)
    		return nums[0] > nums[1] ? nums[0] : nums[1];
    	//處理正常情況	
    	int * maxV = new int[nums.size()];
    
    	maxV[0] = nums[0];
    	maxV[1] = nums[0] > nums[1] ? nums[0] : nums[1];
    
    	for (int i = 2 ; i < nums.size() ; ++i)
    	{
    		maxV[i] = max(maxV[i - 2] + nums[i], maxV[i - 1]);
    	}
    
    	int result = maxV[nums.size() - 1];
    	delete maxV;
    	maxV = NULL;
    	return result;
    }
};

2016-08-31 21:49:51

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

名稱欄目：leetCode198.HouseRobber|動態(tài)規(guī)劃-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://www.aaarwkj.com/article40/pigho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、響應(yīng)式網(wǎng)站、小程序開發(fā)、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)