网址:https://leetcode.com/problems/house-robber/
参考:https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.
容易得出转移方程,然后要考虑各种极端情况。
class Solution { public int rob(int[] nums) { int[] dp = new int[nums.length]; if(nums.length == 0) return 0; else if(nums.length == 1) return nums[0]; else { if(nums.length == 2) { return Math.max(nums[0], nums[1]); } else { dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(int i=2; i<nums.length; i++) { dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]); } return dp[nums.length-1]; } } } }
这么做代码显得稍微繁琐,并且可以把dp数组简化为3个不断更新的变量!
class Solution { public int rob(int[] nums) { int pre1 = 0; int pre2 = 0; int temp = 0; for(int num : nums) { temp = Math.max(num + pre2, pre1); pre2 = pre1; pre1 = temp; } return temp; } }