leetcode：House Robber（動态規劃dp1）

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、當數組為空（即沒有可搶劫的房子）時，傳回0

                  2、當數組元素個數為1時，這時最大搶劫金額（記為maxrob[1]） 即為nums[0].

                  3、當數組元素個數大于1時，我們運用動态規劃（dp）的思想從下向上進行遞推：maxrob[2]取值為前兩個元素中的大者，maxrob[3]取值為元素1,3的組合同元素2相比的大者。我們容易得到遞歸方程：

maxrob[i]=a+nums[i-1];

a=(maxrob[i-2]>maxrob[i-3])?maxrob[i-2]:maxrob[i-3]

即組合目前元素nums[i-1]時，（考慮到不相鄰的特征）需比較組合了其前面2位的元素nums[i-3]的最大組合maxrob[i-2]群組合了其前面3位的元素nums[i-4]的最大組合maxrob[i-3]

                  4、最後還需比較下組合了最後元素的情況群組合了倒數第二位元素的情況，選取較大者作為傳回值即可。

代碼如下：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
         if(nums.empty())
        {
            return 0;
        }
        long long maxrob[n];
        maxrob[1]=nums[0];
          if(n==1)
        {
            return maxrob[1];
        }
        else{
        maxrob[2]=(nums[0]>nums[1])?nums[0]:nums[1];
        maxrob[3]=(nums[0]+nums[2]>nums[1])?nums[0]+nums[2]:nums[1];
        for(int i=4; i <= n; i++){
            if(maxrob[i-2]>maxrob[i-3])
            {
                 maxrob[i]=maxrob[i-2]+nums[i-1];
            }
            else
            {
                maxrob[i]=maxrob[i-3]+nums[i-1];
            }
        }
        return (maxrob[n]>maxrob[n-1])?maxrob[n]:maxrob[n-1];
        }
    }
};
           

第一次在leetcode上做tag為動态規劃的題目，思路還不夠簡潔，不過效果還是達到了的。

看看其他參考解法：　　

一、

這是一個更簡便的方法，也是自下向上進行推演(規則是：每次包含目前元素的最大值組合都是與包含前一進制素的最大值組合相比較的)

class Solution {
public:
    int rob(vector<int>& nums) {
        int f1, f2, i, temp;
        f1 = 0;
        if(nums.size()){
            f2 = nums[0];
            f1 = (nums.size() > 1 && nums[0] < nums[1])? nums[1] : nums[0];
            for(i = 2; i < nums.size(); i++){
                temp = f1;
                f1 = (nums[i] + f2) > f1? (nums[i] + f2) : f1;
                f2 = temp;
            }
        }
        return f1;
    }
};
           

二、

A[i][0]表示第i次沒有搶劫，A[i][1]表示第i次進行了搶劫

即A[i+1][0] = max(A[i][0], A[i][1]).. 那麼rob目前的house，隻能等于上次沒有rob的+money[i+1], 則A[i+1][1] = A[i][0]+money[i+1].

實際上隻需要兩個變量儲存結果就可以了，不需要用二維數組

class Solution {  
public:  
    int rob(vector<int> &nums) {  
        int best0 = 0;   // 表示沒有選擇目前houses  
        int best1 = 0;   // 表示選擇了目前houses  
        for(int i = 0; i < nums.size(); i++){  
            int temp = best0;  
            best0 = max(best0, best1); // 沒有選擇目前houses，那麼它等于上次選擇了或沒選擇的最大值  
            best1 = temp + nums[i]; // 選擇了目前houses，值隻能等于上次沒選擇的+目前houses的money  
        }  
        return max(best0, best1);  
    }  
};
           

三、跟我的差不多，但是有些許改進。特别是nums[2] = nums[0]+nums[2]的處理。

class Solution {
public:
    int rob(vector<int> &nums) {
        if(nums.empty())
        {
            return 0;
        }
        int res = 0;
        int length = nums.size();
        if(1 == length)
        {
            return nums[0];
        }
        if(length >= 3)
        {
            nums[2] = nums[0]+nums[2];
        }
        for(int i = 3; i < length; i++)
        {
            if(nums[i-2]>nums[i-3])
            {
                nums[i] += nums[i-2];
            }
            else
            {
                nums[i] += nums[i-3];
            }
             
        }
        return (nums[length-2]>nums[length-1])? nums[length-2]:nums[length-1];
         
    }
};
           

　　

　　

　

轉載于:https://www.cnblogs.com/carsonzhu/p/4651057.html