leetcode198

public class Solution {
    public int Rob(int[] nums) {
        int i = 0;
            int e = 0;
            for (int k = 0; k < nums.Length; k++)
            {
                int tmp = i;
                i = nums[k] + e;
                e = Math.Max(tmp, e);
            }
            return Math.Max(i, e);
    }
}

https://leetcode.com/problems/house-robber/#/description

/*
你是一个专业强盗，并计划沿街去盗窃每一个住户。
每个房子都有一定量的现金，阻止你盗窃的唯一阻碍是相邻的两个房子之间有安全系统。
一旦这两个房子同时被盗窃，系统就会自动联系警察。
给定一系列非负整数代表每个房子的金钱，
求出在不惊动警察的情况下能盗窃到的最大值*/

上面的程序不是很容易理解，略微进行修改如下：

public class Solution
    {
        public int Rob(int[] nums)
        {
            if (nums.Length > 0)
            {
                int i = nums[0];
                int e = 0;
                for (int k = 1; k < nums.Length; k++)
                {
                    var tmp = nums[k] + e;//抢当前的房间的累积金额，临时存储
                    e = Math.Max(i, e);
                    //i：不抢当前房间但是抢前一个房间   
                    //e：不抢当前房间同时不抢前一个房间
                    //两者大的是新的e：不抢当前房间累积金额
                    i = tmp;//抢当前房间的累积金额
                }
                return Math.Max(i, e);
            }
            else
            {
                return 0;
            }
        }
    }

经过一段时间学习，重新做这道题，使用了更加容易理解的写法：

public class Solution
    {
        public int Rob(int[] nums)
        {
            var len = nums.Length;
            if (len == 0)
            {
                return 0;
            }
            else if (len == 1)
            {
                return nums[0];
            }
            else if (len == 2)
            {
                return Math.Max(nums[0], nums[1]);
            }
            //len>=3
            //var robmoney = 0;//累计的抢夺的钱
            var money = new int[len];//记录截止到当前位置最多的金额
            money[0] = nums[0];
            money[1] = Math.Max(nums[0], nums[1]);
            for (int i = 2; i < len; i++)
            {
                //如果当前房间-1已经被抢了，那么当前房间不能抢 新的累计金额是之前最大金额

                //如果当前房间-1没有被抢，则新的累计金额是 之前最大金额+当前房间金额
                money[i] = Math.Max(money[i - 1], money[i - 2] + nums[i]);
                //robmoney += money[i];
            }

            return money[len-1];
        }
    }

用money数组记录，到当前i位置为止，所抢夺的最大的金额。

决定当前的i位置是否要抢里面的钱，根据i-1房间是否已经抢过来判断。

如果i-1房间被抢，那i位置房间的金额就不可以再抢。如果i-1房间没有被抢，则i位置最大金额就是i-2的最大金额+i房间的金额。

每次记录的是，截止到目前位置，最大的金额数。也就是这两种方案中较大的一种。

补充一个python的版本：

 1 class Solution:
 2     def rob(self, nums: List[int]) -> int:
 3         n = len(nums)
 4         if n == 0:
 5             return 0
 6         elif n == 1:
 7             return nums[0]
 8         elif n == 2:
 9             return max(nums[0],nums[1])
10         
11         dp = [0] * (n + 1)
12         dp[0] = 0
13         dp[1] = nums[0]
14         for i in range(2,n+1):
15             dp[i] = max(dp[i-2]+nums[i-1],dp[i-1])
16         return dp[n]

定义dp，长度n + 1，表示“到当前房间为止，所获得的最多钱数”。

dp[0]初始化为0，方便计算。

最后返回dp[n]为所求。

关键的公式是第15行，表示：当前房间能获得的最多钱数，是两种策略选择其一：

策略1:抢夺当前房间的钱，则抢夺后获得的金钱数量为，跳过前1个房间，也就是“上上个”房间所获得的最多金钱 + 当前房间的金钱

策略2:不抢夺当前房间的钱，则抢夺后（实际上没有抢）的金钱和“上个”房间所获得的最多金钱值一样。

比较这两种策略，选择多的作为dp[i]的结果，即表示截止到当前房间，所获得的最多的金钱数量。

leetcode198

推荐阅读