leetcode 198: House Robber//Leetcode 213 : House Robber II

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.

这个题目问的是能盗取的最大的钱数，通过分析肯定是属于一维dp的题目，而一维DP的递推规律也很好找，即跳过左边的房子看盗取之前的房子哪个钱数多。M[i]表示盗到第i 家包含i在内的最多钱数。

时间复杂度是O(n^2). 空间复杂度O(n).


class Solution {
public:
    //use dp
    int rob(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        int M[nums.size()];
        //base case
        M[0] = nums[0];
        int rst = M[0];
        for (int i = 1; i < nums.size();i++) {
            if (i == 1) M[1] = nums[1];
            else {
                int j = i-2;
                int maxl = 0;
                for (; j >= 0; j--) {
                    maxl = max(M[j] + nums[i], maxl);
                }
                M[i] = maxl;
            }
            rst = max(rst, M[i]);
        }
        return rst;
    }
};

House RobberII

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.

 题目分析： 这个题目是house robber的follow up， 如果所有房子是一个circle，怎么处理，其实举几个列子发现，偷东西只可能两种情况，一种是偷了最后一家，那么就不能偷第一家， 所以偷的房子范围是 1-size-1， 另一种是不偷最后一家，那么就可以偷第一家，所以偷房子的范围是0-size-2， 最后取这两种情况下的较大值，而这两种情况下的最大值的可以通过house robber1的dp方法来做。

class Solution {
private:
//get the max money from start to end
    int helper(vector<int> &nums, int start, int end) {
        int rst = 0;
        //sanity check
        if (start > end) return rst;
        int M[end - start +1];
        //base caes
        M[0] = nums[start];
        rst = M[0];
        for (int i = 1; i < end-start+1; i++) {
            if (i == 1) {
                M[i] = nums[start+1];
            } else {
                int tmp_max = INT_MIN;
                for (int j = i-2; j >= 0; j--) {
                    tmp_max = max(tmp_max, M[j] + nums[start+i]);
                }
                M[i] = tmp_max;
            }
            rst = max(rst, M[i]);
        }
        return rst;
    }
public:
    int rob(vector<int>& nums) {
        //sanity cehck
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        //case 1 : stole the end
        int e1 = helper(nums, 1, nums.size()-1);
        //case 2: didn't stole the end
        int e2 = helper(nums, 0, nums.size()-2);
        return max(e1, e2);
    }
};

updated;
这个题目可以进一步优化到O（n）的时间复杂度，只要改变一下M[i]的定义： 走到第i家能盗到的最大钱数，最后直接返回M[size-1]就可以了，比第一种方法效率高。 

class Solution {
public:
    //use dp
    int rob(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        int M[nums.size()];
        //base case
        M[0] = nums[0];
        int rst = M[0];
        for (int i = 1; i < nums.size();i++) {
            if (i == 1) M[1] = max(nums[1],nums[0]);
            else {
                M[i] = max(M[i-2] + nums[i], M[i-1]);
            }
        }
        return M[nums.size()-1];
    }
};

通过这个题目发现，dp解题时M[i]的定义不同，解法的效率是不同的，要多想几种可能解的M[i]