本文主要是介绍阿亮的算法之路——213. 打家劫舍 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
动态规划集中练习
题目描述
题目链接:https://leetcode-cn.com/problems/house-robber-ii/
解题思路
动态规划的典型题目,是上一个打家劫舍 题目的升级版,不同的是,上一个是一个单链,这个是一个环形。其实核心都是动态规划,但是就算上一个题会做,这个题也不一定会做,这里还有一点需要考虑和处理。(当然方法可能不止一种),
如果以上来就考虑:环形的怎么写状态转移方程,那么就很难跳出来。其实,我们想:换成了环形之后,有什么影响?其实影响就是:偷第一个就不能偷最后一个,偷最后一个就不能偷第一个
往这个方向思考,就可以很容易的解出来。先假设不偷第一个,用动态规划求出到最后一个的最大值。再不偷最后一个,把前n-1个的最大值算出来。
再两者比较,较大的那个就是最终答案。
状态定义和状态转移方程和之前那个题都是一样的:https://blog.csdn.net/ql_7256/article/details/107523159
提交代码
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%。
这篇关于阿亮的算法之路——213. 打家劫舍 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!