0198

方法一 简单枚举
复杂度为2ⁿ, 实际上不可接受

int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}

class Solution {
public:
    int solve(int idx, vector<int>& nums){
        if(idx<0)
            return 0;
        return max(nums[idx]+solve(idx-2,nums), solve(idx-1, nums));
    }
    int rob(vector<int>& nums) {
        int len = nums.size();
        return solve(len-1, nums);
    }
};

方法二 记忆搜索

C++：book变量不能用static修饰

int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}

class Solution {
public:
    vector<int> book;
    int solve(int idx, vector<int>& nums){
        if(idx<0)
            return 0;
        if(book[idx]!=-1){
            return book[idx];
        }
        book[idx]=max(nums[idx]+solve(idx-2,nums), solve(idx-1,nums));
        return book[idx];
    }
    int rob(vector<int>& nums) {
        int len = nums.size();
        book = vector<int> (len,-1);
        return solve(len-1, nums);
    }
};

Java: 自带max函数，且book用static，

class Solution {
    public static int[] book;
    public int solve(int idx, int[] nums){
        if(idx<0)
            return 0;
        if(book[idx]!=-1){
            return book[idx];
        }
        book[idx]=Math.max(nums[idx]+solve(idx-2,nums), solve(idx-1,nums));
        return book[idx];
    }
    public int rob(int[] nums) {
        int i;
        int len=nums.length;
        book=new int[len];
        for(i=0;i<len;++i){
            book[i]=-1;
        }
        return solve(len-1,nums);
    }
}

动态数组：修改下面一行就OK
book = new int(len); =>book = new int[len];

int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int* book=NULL;
class Solution {
public:

    int solve(int idx, vector<int>& nums){
        if(idx<0)
            return 0;
        if(book[idx]!=-1){
            return book[idx];
        }
        book[idx]=max(nums[idx]+solve(idx-2,nums), solve(idx-1, nums));
        return book[idx];
    }
    int rob(vector<int>& nums) {
        int i;
        int len = nums.size();
        book = new int[len];
        for(i=0;i<len;i++)
            book[i]=-1;
        return solve(len-1, nums);
    }
};