手机网站建设多少钿,做360手机网站优化快,万网网站后台管理系统,学院网站建设工作会议力扣爆刷第77天–动态规划一网打尽打家劫舍问题 文章目录 力扣爆刷第77天--动态规划一网打尽打家劫舍问题一、198.打家劫舍二、213.打家劫舍II三、337.打家劫舍 III 一、198.打家劫舍
题目链接#xff1a;https://leetcode.cn/problems/house-robber/ 思路#xff1a;小偷不…力扣爆刷第77天–动态规划一网打尽打家劫舍问题 文章目录 力扣爆刷第77天--动态规划一网打尽打家劫舍问题一、198.打家劫舍二、213.打家劫舍II三、337.打家劫舍 III 一、198.打家劫舍
题目链接https://leetcode.cn/problems/house-robber/ 思路小偷不能连续两家偷由此可以定义dp[i]表示小偷经过[0,i]所能获取到的最大金额那么我们可以得到递推公式: dp[i] Math.max(dp[i-1], dp[i-2]nums[i]); 即如果偷nums[i]家就不能偷前一家为dp[i-2]nums[i]如果不偷当前这家那金额就要维持为经过前一家时的结果。 很简单的题目标准的动态规划进行状态选择。 标准写法
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] Math.max(nums[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];}
}优化写法
class Solution {public int rob(int[] nums) {if (nums.length 1) return nums[0];int a nums[0], b Math.max(nums[0], nums[1]);for (int i 2; i nums.length; i) {int c Math.max(b, anums[i]);a b;b c;}return b;}
}二、213.打家劫舍II
题目链接https://leetcode.cn/problems/house-robber-ii/ 思路本题和上一题不同之处是房间首尾相连那么也很简单直接从两个范围求第一个范围[0, len-1] 第二个范围[1, len]分别从这两个范围一个只含头一个只含尾其他的和上一题一样。
class Solution {public int rob(int[] nums) {if(nums.length 1) return nums[0];if(nums.length 2) return Math.max(nums[0], nums[1]);return Math.max(getMax(nums, 0, nums.length-1), getMax(nums, 1, nums.length));}int getMax(int[] nums, int s, int e) {int[] dp new int[nums.length];dp[s] nums[s];dp[s1] Math.max(nums[s], nums[s1]);for(int i s2; i e; i) {dp[i] Math.max(dp[i-1], dp[i-2]nums[i]);}return dp[e-1];}
}三、337.打家劫舍 III
题目链接https://leetcode.cn/problems/house-robber-iii/description/ 思路二叉树形态的打家劫舍其实也很简单每个节点有两种状态分别是抢不与抢后序遍历返回dp数组有了左右子树的dp数组即可计算当前节点的dp数组计算后返回以此递归即可解题。
/*** 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 {public int rob(TreeNode root) {int[] dp traverse(root);return Math.max(dp[0], dp[1]);}// 0 偷 1 不偷int[] traverse(TreeNode root) {if(root null) return new int[2];int[] left traverse(root.left);int[] right traverse(root.right);int[] dp new int[2];dp[0] root.val left[1] right[1];dp[1] Math.max(left[0], left[1]) Math.max(right[0], right[1]);return dp; }}
