Day50.算法训练

算法训练"/>

Day50.算法训练

198. 打家劫舍

class Solution {public int rob(int[] nums) {if(nums.length ==1){return nums[0];}int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Integer.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}

213. 打家劫舍 II

class Solution {public int rob(int[] nums) {if (nums.length == 1) {return nums[0];}int rob1 = rob2(Arrays.copyOfRange(nums, 0, nums.length - 1));int rob2 = rob2(Arrays.copyOfRange(nums, 1, nums.length));return Integer.max(rob1, rob2);}public int rob2(int[] nums) {if (nums.length == 1) {return nums[0];}int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Integer.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}}

337. 打家劫舍 III

class Solution {public int rob(TreeNode root) {int[] ints = rob2(root);return Integer.max(ints[0], ints[1]);}public int[] rob2(TreeNode root) {if (root == null) {return new int[]{0, 0};}int[] leftDp = rob2(root.left);int[] rightDp = rob2(root.right);int val1 = Integer.max(leftDp[0], leftDp[1]) + Integer.max(rightDp[0], rightDp[1]);int val2 = root.val + leftDp[0] + rightDp[0];return new int[]{val1, val2};}
}