韶关住房和城乡建设网站,创建免费网站,wordpress哪个seo工具好,邵阳做网站建设代码随想录算法训练营Day50|动态规划9 文章目录 代码随想录算法训练营Day50|动态规划9一、198.打家劫舍二、213.打家劫舍II三、337.打家劫舍 III 一、198.打家劫舍
class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) return 0;if (nums.length …代码随想录算法训练营Day50|动态规划9 文章目录 代码随想录算法训练营Day50|动态规划9一、198.打家劫舍二、213.打家劫舍II三、337.打家劫舍 III 一、198.打家劫舍
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(dp[0], nums[1]);for (int i 2; i nums.length; i) {dp[i] Math.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 null || nums.length 0)return 0;int len nums.length;if (len 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x 0, y 0, z 0;for (int i start; i end; i) {y z;z Math.max(y, x nums[i]);x y;}return z;}
}三、337.打家劫舍 III
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {// 1.递归去偷超时public int rob(TreeNode root) {int[] res robAction(root);return Math.max(res[0], res[1]);}int[] robAction(TreeNode root) {int res[] new int[2];if (root null)return res;int[] left robAction(root.left);int[] right robAction(root.right);res[0] Math.max(left[0], left[1]) Math.max(right[0], right[1]);res[1] root.val left[0] right[0];return res;}}
