第198题---House Robber

• 题意描述

  • 一个vector中表示一系列的房屋的财物价值，小偷不能偷连续两家的财物，否则就会自动报警，问小偷怎么偷，才能偷得最大的财物价值

• 思路一

  • 分为奇数和偶数统计相关的信息，奇数项，只能由奇数项+当前的财物或者上一个偶数项中的最大值决定，偶数项同样，最后求两个数的大小

    class Solution {
    public:
        int rob(vector<int>& nums) {
            int a = 0;
            int b = 0;
            
            for(int i = 0; i < nums.size(); ++i) {
                if(i % 2 == 0) {
                    a = max(a + nums[i], b);
                } else {
                    b = max(a, b + nums[i]);
                }
            }
            return a > b ? a : b;
        }
    };

• 思路二

  • 用两个变量表示当前房屋偷还是不偷的财物的数量，偷=上次不偷的+本次偷得；不偷=上次偷或者不偷的最大值

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

• 思路三

  • 动态规划的算法，当前状态的值由上一次的值和上上一次值+当前房屋状态的值的最大值决定

     int max(int a, int b) {
         return a > b ? a : b;
     }
    
    int rob(int* nums, int numsSize) {
        int* d;
    
        d = (int*) malloc (numsSize * sizeof(nums[0]));
    
        d[0] = nums[0];
        d[1] = max (nums[0], nums[1]);
    
        for (int i = 2; i < numsSize; i++) {
            d[i] = max(d[i-2]+nums[i], d[i-1]);
        }
    
        return d[numsSize-1];
    }