leetcode 약탈 1, 2, 3 (dp + 재 귀)

leetcode 가 집 을 털 고 집 을 강탈 하 는 1 개의 뜻: 하나의 배열 을 정 하고 인접 한 숫자 를 더 할 수 없 으 며 나머지 숫자 는 임의로 더 할 수 있 습 니 다. 다음 상황 에서 가장 큰 것 과 얼마나 많은 생각 이 냐 고 물 었 습 니 다. 주제 의 뜻 을 이해 한 후에 이 문제 의 최대 와 최대 가 동태 적 으로 증가 하 는 과정 임 을 알 수 있 습 니 다. 그리고 이전에 구 한 최대 의 합 에 의존 하면 우 리 는 dp 로 해결 할 수 있 습 니 다.dp 의 동적 방정식 은 dp [i] = max (dp [i - 2] + nums [i], dp [i - 1])
코드 는 다음 과 같 습 니 다:

public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        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] = nums[1];
        dp[1] = Math.max(dp[0],dp[1]);
        dp[2] = dp[0]+nums[2];
        dp[2] = Math.max(dp[2],dp[1]);
        for(int i = 2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }

코드 공간 에 대한 복잡 도 를 계속 합 니 다. 우 리 는 dp [i - 2] 와 dp [i - 1] 이전의 데이터 만 사용 할 수 없 기 때문에 두 개의 임시 변수 로 저장 할 수 있 습 니 다. 최적화 후 코드 는 다음 과 같 습 니 다.

  public int rob(int[] num) {
    int prevMax = 0;
    int currMax = 0;
    for (int x : num) {
        int temp = currMax;
        currMax = Math.max(prevMax + x, currMax);
        prevMax = temp;
    }
    return currMax;
}

leetcode 가 집 을 약탈 하 는 2 가지 의미: 1 을 바탕 으로 머리 와 꼬리 도 서로 인접 하지 못 한다. 사고: 최대 와 의 영향 은 두 가지 상황 으로 나 눌 것 이다. 1. 머리 를 강탈 하지만 꼬리 를 강탈 하지 않 으 면 0 - n - 1 2. 거 리 를 강탈 하지 않 지만 꼬리 를 강탈 하면 1 - n 이 2 자 에 게 최대 ans 를 유지 하면 된다.
코드 는 다음 과 같 습 니 다:

class Solution {
 public int robs(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        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] = nums[1];
        dp[1] = Math.max(dp[0],dp[1]);
        dp[2] = dp[0]+nums[2];
        dp[2] = Math.max(dp[2],dp[1]);
        for(int i = 2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
    public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        return Math.max(robs(Arrays.copyOfRange(nums,0,nums.length-1)),robs(Arrays.copyOfRange(nums,1,nums.length)));

    }
}

leetcode 가 집 을 약탈 하 는 3 가지 의미: 이 진 트 리 유형의 집에 서 약탈 하 는 것 은 연결 되 어 있 는 점 을 만족 시 키 고 생각 을 빼 앗 을 수 없습니다. 모든 노드 를 재 귀적 으로 유지 하 는 두 가지 상황 1. 두 결점 참여 + 손자 결점 과 2. 머리 없 는 결점 참여 + 아들 결점 의 합
코드 는 다음 과 같 습 니 다:

class Solution {
   public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        int lval = rob(root.left);
        int rval = rob(root.right);
        int llval = 0;
        int lrval = 0;
        int rrval = 0;
        int rlval = 0;
        if(root.left!=null){
            llval = rob(root.left.left);
            lrval = rob(root.left.right);
        }
        if(root.right!=null){
            rrval = rob(root.right.right);
            rlval = rob(root.right.left);
        }
        return Math.max(lval+rval,llval+lrval+rrval+rlval+root.val);
    }
}

계속 이 사고방식 에 따라 최적화 하 다

class Solution {
   
    public int rob(TreeNode root){
        int[] res = doRob(root);
        return Math.max(res[0],res[1]);
    }
    public int[] doRob(TreeNode root){
        int[] res = new int[2];
        if(root==null){
            return res;
        }
        int[] left = doRob(root.left);
        int[] right = doRob(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;
    }
}