198. House Robber

198. 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.

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.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

My Solutions:

用dp做，可以用一个dp【】储存或者只用一个int lastP

dp【i】 = Math.max(dp[i - 1], dp[i - 2] +nums[i - 1]) 表示可以

• 抢劫在当前之前的一家（不抢劫当前家庭）: dp[i - 1]

• 或者抢劫当前家和之前skip 1的一家: dp[i - 2] + nums[i - 1]

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len <= 0) return 0;
        int[] dp = new int[len + 1]; // 注意这里是+1
        dp[0] = 0; // rob nothing before house 1
        dp[1] = nums[0]; //house 1
        for (int i = 2; i <= len; i++) { //go through from house 2 //注意这里是i<=len
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
        }
        return dp[len];
        
// 因为只需要记录两个数字，所以也可以直接用两个int variable记录        
// 假设【0,1,2】现在在2号家庭。lastP代表抢劫了0号家庭，profit代表抢劫了1号家庭
//         int lastP = 0, profit = 0;
//         for (int i = 0; i < nums.length; i++) {
//             int temp = lastP; // 抢劫skip 1前一家的利润
//             lastP = profit; // 抢劫上一家的利润
//             profit = Math.max(profit, nums[i] + temp); //表示当前可以获得的最大利润
//         }
//         return profit;
    }
}