動態規劃經典題

04-29

#日記第XX天，最近又要開始學習Javascript了

昨天我分享的是C++裡面的Hash函數，如果是僅僅局限於使用，我想再做幾個題目就行了，其它的話就還要花點功夫了。

今天我要分享的是動態規劃(Dynamic Programming)，這裡給出的解釋是來自Wikipedia，大家要習慣看英文解釋哦。

因為在LeetCode做到兩個比較經典的題--`House Robber Ⅰ&Ⅱ`，所以分享給大家。Robber就是盜賊的意思。

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.

題目的大致意思是在一條街上有相鄰的幾個房子，每個房子用數字代替他們藏有的錢，盜賊只能間隔的偷每個房子，不能偷相鄰房子的錢，問如何才能使偷的錢最多！

這種題就是典型的動態規划了。假設當前的房子編號為i,用re[i]表示之前獲得的最大利益，則re[i]存在兩種狀態，i房要是偷的話就是re[i] = re[i-2] + nums[i] (注意此時r[i-1]不能偷),如果i房不偷，則re[i] = re[i-1],綜上則有re[i] = max(re[i-1],re[i-2]+nums[i])。

代碼

class Solution {public: int rob(vector& nums) { int temp1 = 0,temp2 = 0,re = 0; for(auto x:nums){ re = max(temp1 +x,temp2); temp1 = temp2; temp2 = re; } return re; }};

第二題：

在第一題基礎上增加了一個條件，即原來的一條街變成了一個環，其實這並不是很難去解決，因為可以把環拆開，意思就是第一個不偷，那麼最後一個偷；最後一個不偷，那麼第一個就會偷。

House Robber Ⅱ：

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.

參考代碼

class Solution {public: int rob(vector& nums) { if(nums.size()==0)return 0; if(nums.size()<=3)return *max_element(nums.begin(),nums.end()); vectornums1; nums1.assign(nums.begin()+1,nums.end());//頭不偷，尾偷 vectornums2; nums2.assign(nums.begin(),nums.end()-1);//頭偷，尾不偷 return max(maxProfit(nums1),maxProfit(nums2)); }private: int maxProfit(vectornums){ int temp1 =0,temp2 =0,re = 0; for(auto x:nums){ re = max(temp1 +x,temp2); temp1 = temp2; temp2 = re; } return re;}};