Open Shawngbk opened 7 years ago
这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。 这是一道动态规划问题。 我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和。 状态转移方程：
dp[0] = num[0] （当i=0时） dp[1] = max(num[0], num[1]) （当i=1时） dp[i] = max(num[i] + dp[i - 2], dp[i - 1]) （当i !=0 and i != 1时） //理清思路： //最值方案问题，考虑采用动态规划 //令dp[i][0]表示第i个房子是获取的最大值 //无论什么时候最后一个人要么是偷要么不偷 //如果最后一个是偷，显然dp[i] = dp[i - 2]+nums[i]; //如果最后一个是不偷，dpV[i]=dp[i-1]; public class Solution { public int rob(int[] nums) { if(nums == null || nums.length == 0) { return 0; } if(nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(int i = 2; i < nums.length; i++) { dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); } return dp[nums.length-1]; } }
Airbnb Linkedin
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。 这是一道动态规划问题。 我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和。 状态转移方程：
dp[0] = num[0] （当i=0时） dp[1] = max(num[0], num[1]) （当i=1时） dp[i] = max(num[i] + dp[i - 2], dp[i - 1]) （当i !=0 and i != 1时） //理清思路： //最值方案问题，考虑采用动态规划
//令dp[i][0]表示第i个房子是获取的最大值 //无论什么时候最后一个人要么是偷要么不偷 //如果最后一个是偷，显然dp[i] = dp[i - 2]+nums[i]; //如果最后一个是不偷，dpV[i]=dp[i-1]; public class Solution { public int rob(int[] nums) { if(nums == null || nums.length == 0) { return 0; } if(nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(int i = 2; i < nums.length; i++) { dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); } return dp[nums.length-1]; } }