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: 4Explanation: 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: 12Explanation: 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.

 

分析：这个题目翻译如下：一个数组nums，求这个数组不相邻的元素和最大是多少。很容易理解这个题和动态规划有关，因为某个位置取不取和前面的状态有关。这种类似找极值的问题都考虑用动态规划求解。首先维护一个数组dp，dp[i]表示到第i个位置可以获得最大的数字和是多少。下面的关键就是如何找到状态转移方程了。针对这个题目，我们以[2,7,9,3,1]为例：

0位置最大收益：肯定是dp[0]=2；

1位置最大收益：有两种可能，一种是0位置取了，1位置就不取；第二种是0位置不取，1位置取；也就是：dp[1] = max{dp[0],dp[1]}=9;

2位置最大收益：也有两种可能，一种是0位置最大收益加上2位置的值，一种是取1位置最大收益，不取2位置最大收益，即：dp[2] = max{dp[1],dp[0]+nums[2]}=11;

3位置最大收益：原理同上，即：dp[3]=max{dp[2],dp[1]+nums[3]}=11;

4位置最大收益：原理同上，即：dp[4]=max{dp[3],dp[2]+nums[4]}=12;

所以输出dp[4]和dp[3]的最大值：12。

由上面的分析，我们就找到了从2位置开始的状态转移方程：dp[i]=max{dp[i-1],dp[i-2]+nums[i]  (i>=2)。

代码如下：

1 public int rob(int[] nums) { 2         if ( nums == null || nums.length == 0 ) return 0; 3         if ( nums.length == 1 ) return nums[0]; 4         int[] dp = new int[nums.length]; 5         dp[0] = nums[0]; 6         dp[1] = Math.max(nums[0],nums[1]); 7         for ( int i = 2 ; i < nums.length ; i ++ ){ 8             dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]); 9         }10         return Math.max(dp[nums.length-1],dp[nums.length-2]);11     }

      运行时间3ms，看了一下1ms、0ms的答案，都是舍弃dp数组，直接用一个变量表示。我觉得这反而不能体现出动态规划的思想，所以就不整理了。理解动态规划的思想才是最重要的。