题解 | #打家劫舍(二)#

package com.hhdd.dp;

import java.util.Arrays;

/**
 * 不会做
 *
 * @Author huanghedidi
 * @Date 2022/8/7 1:04
 */
public class 打家劫舍2 {

    public static void main(String[] args) {
        int[] arr = {1, 3, 6};
        int res = rob(arr);
        System.out.println("res = " + res);
    }

    /**
     * 使用dp解决
     * dp[i]代表截至i位置能够偷取的最大现金
     * 因为题目限制是个环形，即头位置和尾部位置不能同时获取
     * 故分别对0到length-1 和1到length的部分求值，并取出它们的最大值
     * 即最终结果
     * 如何理解：可以画个交集图，如果取了头部则不会取尾最终结果在前部分，取尾则在后部分
     * 比较难理解
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        // write code here
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 复制数组
        int[] arr1 = Arrays.copyOfRange(nums, 0, nums.length - 1);
        int[] arr2 = Arrays.copyOfRange(nums, 1, nums.length);
        int res = Math.max(solution(arr1), solution(arr2));
        return res;
    }

    public static int solution(int[] arr) {
        if (arr.length == 2) {
            return Math.max(arr[0], arr[1]);
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = arr[1] > dp[0] ? arr[1] : dp[0];
        dp[2] = arr[2] + dp[0] > dp[1] ? arr[2] + dp[0] : dp[1];
        for (int i = 3; i < arr.length; i++) {
            int tmp = Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i]);
            dp[i] = Math.max(dp[i - 1], tmp);
        }
        return dp[dp.length - 1];
    }

}