집 약탈

20362 단어 leetcode

leetcode213 - 집 약탈 2 원제 링크


제목의 뜻을 약술하다.


입력:nums[]int, 비 마이너스 정수 그룹 작업:nums 그룹에서 인접하지 않은 수를 추출하고 첫 번째와 마지막 것을 동시에 추출할 수 없습니다. 최대 출력:max int

해법 분석


동적 기획
1.       ,                   .      leetcode---    1
           solve(int[] nums)
      : 
	dp[i]=max(dp[i-2],dp[i-3])
2.                    ,    ,
	         solve(nums[0:nums.length-1])
	   solve(nums[1:nums.length])
	        2 solve()  

복잡도 분석
시간 복잡도: O(n) 공간 복잡도: O(n)
최적화
코드:
  • JAVA Edition:
  • class Solution {
        public int rob(int[] nums) {
            if(nums.length == 0) return 0;
            else if(nums.length == 1) return nums[0];
            int[] a = new int[nums.length];
            int[] b = new int[nums.length];
            for(int i = 0; i < nums.length - 1; i++) {
                a[i] = nums[i];
                b[i] = nums[i + 1];
            }
            return Math.max(solve(a),solve(b));
        }
        
        public int solve(int[] nums) {
            if(nums.length == 0) {
                return 0;
            } else if(nums.length == 1) {
                return nums[0];
            } else 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[2] = nums[0] + nums[2];
            for(int i = 3; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 2],dp[i - 3]) + nums[i];
            }
            return Math.max(dp[nums.length - 1],dp[nums.length - 2]);
        }
    }
    
  • Go Edition:
  • func rob(nums []int) int {
        length := len(nums)
        if length == 0 {
        	return 0
        } else if length == 1 {
        	return nums[0]
        }
        //    ...
        return max(solve(nums[0:length - 1]),solve(nums[1:length]))
    }
    
    func solve(nums []int) int {
    	length := len(nums)
    	if length == 0 {
    		return 0
    	} else if length == 1 {
    		return nums[0]
    	} else if length == 2 {
    		return max(nums[0],nums[1])
    	}
    	var dp [100000]int
    	dp[0] = nums[0]
    	dp[1] = nums[1]
    	dp[2] = nums[0] + nums[2]
    	for i := 3; i < length; i++ {
    		dp[i] = max(dp[i - 2],dp[i - 3]) + nums[i]
    	}
    	return max(dp[length - 1],dp[length - 2])
    }
    
    func max(a int, b int) int {
    	if a > b {
    		return a
    	} else {
    		return b
    	}
    }
    

    좋은 웹페이지 즐겨찾기