【leetcode】House Robber & House Robber II(middle)

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.
 
사고방식: 귀속 시간 초과를 쓰기 시작했다.오랜만에 반응해서 동적 기획을 해야 돼.
반복 코드:

int rob(vector<int> &num) {

        return robsub(num, 0, num.size());

    }

    int robsub(vector<int> &num, int s, int e)

    {

        if(s == e) return 0;

        if(e - s == 1) return num[s];

        return max(robsub(num, s + 1, e), num[s] + ((e - s >= 3) ? robsub(num, s + 2, e) : 0));

    }

동적 계획:

int rob2(vector<int> &num) {

        vector<int> dp(num.size() + 1, 0); // num[i] - 1 

        int ans = 0;

        for(int i = 1; i <= num.size(); i++)

        {

            dp[i] = num[i - 1] + max(((i - 2) >= 0 ? dp[i - 2] : 0), ((i - 3) >= 0 ? dp[i - 3] : 0));

            ans = (ans > dp[i]) ? ans : dp[i];

        }

        return ans;

    }

 
나의 동적 기획 코드는 사용하는 공간이 너무 많아서 사실 두 변수만 앞의 것을 기록하면 된다.

public class Solution {

    public int rob(int[] num) {

        int i = 0;

        int e = 0;

        for (int k = 0; k<num.length; k++) {

            int tmp = i;

            i = num[k] + e;

            e = Math.max(tmp, e);

        }

        return Math.max(i,e);

    }

}

 
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.
 
생각:
한 달 만에 2를 했는데 결국 차례대로 썼다.또 오랜만에 반응이 떠올랐어. 동적 기획이었어.실패야...
하나의 동그라미로 연결되면 우리는 문제를 집 0에서 n-2와 집 1부터 n-1 두 부분으로 분해할 수 있다.
최상의 코드, dp, 공간 절약

int rob2(vector<int>& nums) {

        if(nums.empty()) return 0;

        if(nums.size() == 1) return nums[0];

        int maxMoney = 0;

        int pre = 0, cur = 0;

        //   

        for(int i = 0; i < nums.size() - 1; ++i)

        {

            int tmp = cur;

            cur = nums[i] + pre;

            pre = max(tmp, pre); // 

        }

        maxMoney = max(cur, pre);

        //   

        cur = pre = 0;

        for(int i = 1; i < nums.size(); ++i)

        {

            int tmp = cur;

            cur = nums[i] + pre;

            pre = max(tmp, pre);

        }

        maxMoney = max(maxMoney, max(cur, pre));

        return maxMoney;

    }

 
차등 코드, dp, 그룹 저장

int rob(vector<int>& nums) {

        if(nums.empty()) return 0;

        if(nums.size() == 1) return nums[0];

        int maxMoney = 0;

        vector<int> dp1(nums.size(), 0);

        vector<int> dp2(nums.size(), 0);

        // 

        for(int i = 0; i < nums.size() - 1; ++i)

        {

            dp1[i] = nums[i] + max((i - 2 >= 0) ? dp1[i - 2] : 0, (i - 3 >= 0) ? dp1[i - 3] : 0);

            maxMoney = (dp1[i] > maxMoney) ? dp1[i] : maxMoney;

        }

        // 

        for(int i = 1; i < nums.size(); ++i)

        {

            dp2[i] = nums[i] + max((i - 2 >= 1) ? dp2[i - 2] : 0, (i - 3 >= 1) ? dp2[i - 3] : 0);

            maxMoney = (dp2[i] > maxMoney) ? dp2[i] : maxMoney;

        }

        return maxMoney;

    }

 
최악의 귀속 코드, 시간 초과.

//   

    int rob1(vector<int>& nums) {

        if(nums.empty()) return 0;

        int maxMoney = 0;

        int curMoney = 0;

        recursion(maxMoney, curMoney, 1, nums, false);

        curMoney = nums[0];

        recursion(maxMoney, curMoney, 2, nums, true);

        return maxMoney;

    }



    void recursion(int &maxMoney, int &curMoney, int id, vector<int>& nums, bool isFirstUsed)

    {

        if(id >= nums.size())

        {

            maxMoney = (curMoney > maxMoney) ? curMoney : maxMoney;

        }

        else if(id == nums.size() - 1 && isFirstUsed) //   

        {

            recursion(maxMoney, curMoney, id + 1, nums, isFirstUsed); // 

        }

        else

        {

            int money = nums[id];

            recursion(maxMoney, curMoney, id + 1, nums, isFirstUsed); // 

            curMoney += money; // 

            recursion(maxMoney, curMoney, id + 2, nums, isFirstUsed);

            curMoney -= money;

        }

    }