LeetCode192: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.

這是道動态規劃的問題。 假設給定的vector為[2,3,4,1,6,5] 可以這麼來定義DP的狀态和狀态轉移方程： A[0]表示搶劫前0戶（必須搶第0戶）的錢為2。 A[1]表示搶劫前1戶（必須搶第1戶）的錢為3。因為搶了第1戶，是以不能搶第0戶了。 A[2]表示搶劫前2戶（必須搶第2戶）的錢的A[0]+4。因為搶了第2戶，是以不能搶第1戶。 A[3]表示搶劫前3戶（必須搶第3戶）的錢為max{A[0],A[1]}+1。因為搶了第3戶，是以不能搶第2戶，隻能取A[0]，A[1]中的最大值。 這樣狀态轉移方程為: A[i]=max{A[j],0}+data[i]。0<=j<i-1。 搶劫數目最多的的錢為：max{A[i]}。0<=i<n 基于這個狀态和狀态轉移方程的代碼如下： runtime:0ms

class Solution {
public:
    int rob(vector<int>& nums) {
        int length=nums.size();
        int *A=new int[length];//A[i] represent the money of rob the room of i and less index.
        int maxMoney=0;
        for(int i=0;i<nums.size();i++)
        {
            A[i]=0;
            for(int j=0;j<i-1;j++)
            {
                if(A[j]>A[i])
                    A[i]=A[j];
            }
            A[i]+=nums[i];
            if(A[i]>maxMoney)
                maxMoney=A[i];
        }
        delete [] A;
        return maxMoney;
    }
};
           

這種解法的時間複雜程度是O(N^2)。因為存在兩層的for循環，但是可以發現上面代碼中的第二層for循環其實可以進行一定程度的簡化。因為對于我們定義的A[i]而言，A[i]代表在必須搶劫第i個房間的前提下還搶劫小于第i個索引的房間的最大值。如果我們将A[i]的含義做一點點小的更改，就可以省略掉第二層for循環了。這樣時間複雜程度變成了O(N)。 依然假設給定的vector為nums=[2,3,4,1,6,5]。下面是重新定義的狀态： B[0]表示加入第0戶時搶劫的最大數目為2. B[1]表示接着加入第1戶時搶劫的最大數目為3.即max{2,3}。 B[2]表示接着加入第2戶時搶劫的最大數目為6,即max{B[0]+4,B[1]} B[3]表示接着加入第3戶時搶劫的最大數目為6，即max{B[1]+1,B[2]} ... 現在由于B[i]的含義發生了變化，它代表多加一戶時能搶劫的最多的錢。是以狀态轉移方程也變化為： B[i]=max{B[i-2]+nums[i],B[i-1]}.2<=i<n B[0]=nums[0],B[1]=max{nums[0],nums[1]} 最終要求解的結果是B[n-1]。時間複雜度為O(N)。 runtime:0ms

class Solution {
public:
    int rob(vector<int>& nums) {
        int length=nums.size();
        if(length==0)
            return 0;
        if(length==1)
            return nums[0];
        if(length==2)
            return max(nums[0],nums[1]);
            
        int *B=new int[length]();
        B[0]=nums[0];
        B[1]=max(nums[0],nums[1]);
        for(int i=2;i<length;i++)
        {
            B[i]=max(B[i-2]+nums[i],B[i-1]);
        }
        return B[length-1];
    }
};
           

從上面兩種解法中可以發現定義好了初始狀态和狀态轉移方程之後代碼就很好編寫了。而且同一個問題對狀态的不同定義也會導緻不同的時間複雜程度。

可以發現如果題目對于連續性有要求可以使用第一種思想，如果沒有要求可以使用第二種思想。