阿亮的算法之路——213. 打家劫舍 II

阿亮的算法之路——213. 打家劫舍 II

动态规划集中练习

题目描述

题目链接：/

解题思路

动态规划的典型题目，是上一个打家劫舍 题目的升级版，不同的是，上一个是一个单链，这个是一个环形。其实核心都是动态规划，但是就算上一个题会做，这个题也不一定会做，这里还有一点需要考虑和处理。（当然方法可能不止一种），

如果以上来就考虑：环形的怎么写状态转移方程，那么就很难跳出来。其实，我们想：换成了环形之后，有什么影响？其实影响就是：偷第一个就不能偷最后一个，偷最后一个就不能偷第一个

往这个方向思考，就可以很容易的解出来。先假设不偷第一个，用动态规划求出到最后一个的最大值。再不偷最后一个，把前n-1个的最大值算出来。
再两者比较，较大的那个就是最终答案。

状态定义和状态转移方程和之前那个题都是一样的：

提交代码

    public static int rob(int[] nums){//特判int len = nums.length;if (len == 0) return 0;if (len == 1) return nums[0];if (len <= 2) return nums[0]>nums[1]?nums[0]:nums[1];//如果不偷第一个，int [] dp1 = new int [len-1];dp1[0] = nums[1];dp1[1] = nums[1] > nums[2]?nums[1]:nums[2];for (int i = 2; i < len-1; i++){ dp1[i] = nums[i+1]+dp1[i-2] > dp1[i-1]?nums[i+1]+dp1[i-2]: dp1[i-1]; }//如果不偷最后一个int [] dp2 = new int[len-1];dp2[0] = nums[0];dp2[1] = nums[0]>nums[1]?nums[0]:nums[1];for (int i = 2; i < len-1; i++){ dp2[i] = nums[i]+dp2[i-2] > dp2[i-1]?nums[i]+dp2[i-2]: dp2[i-1]; }//第一个和最后一个肯定只能偷一个，所以返回两者中最大的一个return dp1[len-2] > dp2[len-2] ?dp1[len-2]:dp2[len-2];}

提交成功，但是应该还有有很大的优化空间，这个只能基本完成功能。
提交结果

又是100%，都见怪不怪了。我猜是：如果程序的执行时间不到1毫秒，都会显示超过100%，而这个题，只要做出来，可能用时都不会超过1毫秒。所以很多都是超过100%。