打家劫舍
链状
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解析:动态规划。1dp[i]为偷第i家时最大金额。2若是0，1的情况作出特殊说明，减少计算。3dp[i] = Math.max(dp[i-1],dp[i-2]+nums[])class Solution { public int rob(int[] nums) { //0的情况 if(nums.length == 0){ return 0; } //1的情况，减少计算 if(nums.length == 1){ return nums[0]; } int[] dp = new int[nums.length+1]; dp[1] = nums[0]; for(int i=2;i<=nums.length;i++){ //递推关系式 if(dp[i-2]+nums[i-1] > dp[i-1]){ dp[i]=dp[i-2]+nums[i-1]; }else{ dp[i] = dp[i-1]; } } return dp[nums.length]; } }环状
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
解析:其实递推方程是一样的。我们可以用两个数组来记录两种情况。初始化不一样，得出两种情况。import java.util.*; class Solution { public int rob(int[] nums) { int m =nums.length; if(m == 0){ return 0; } if(m == 1){ return nums[0]; } int[] dp0 = new int[m+1];//不偷第一间,dp[i]为偷第i间的能获取最大金额 int[] dp1 = new int[m+1];//偷第一间 dp0[1] = 0; dp0[2] = nums[1]; dp1[1] = nums[0]; dp1[2] = nums[0]; for(int i = 2;i<=m;i++){ dp0[i] = Math.max(dp0[i-1],dp0[i-2]+nums[i-1]); dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]); } return Math.max(dp0[m],dp1[m-1]);//偷了第一间之后，不能偷第m间，返回的是m-1间。 } }
投递拼多多集团-PDD等公司10个岗位 >
