提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章来源地址https://www.toymoban.com/news/detail-728264.html
前言
一、力扣198. 打家劫舍
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]);
}
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-2] + nums[i], dp[i-1]);
}
return dp[dp.length-1];
}
}
二、力扣213. 打家劫舍 II
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]);
}
int a = fun(nums, 0, nums.length-2);
int b = fun(nums, 1, nums.length-1);
return Math.max(a,b);
}
public int fun(int[] nums, int start, int end){
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start+1]);
for(int i = start+2; i <= end; i ++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[end];
}
}
三、力扣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 {
public int rob(TreeNode root) {
int[] res = fun(root);
return Math.max(res[0], res[1]);
}
public int[] fun(TreeNode root){
int[] arr = new int[2];
if(root == null){
return arr;
}
//0不偷, 1 偷
int[] left = fun(root.left);
int[] right = fun(root.right);
arr[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
arr[1] = root.val + left[0] + right[0];
return arr;
}
}
文章来源:https://www.toymoban.com/news/detail-728264.html
到了这里,关于代码随想录二刷day48的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!