打家劫舍Java

【力扣算法题】打家劫舍-动态规划_哔哩哔哩_bilibili

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

这里房屋的排列是一条线

public static void main(String[] args) {
//        int[] arr = {1,2,3,1};
        int[] arr = {2,7,2,9,2,1};
//        int[] arr2 = {7,2,2,7};
        System.out.println("最大数为:" + maxMoney(arr));
        System.out.println("最大数为:" + max(arr, arr.length));
        System.out.println("最大数为:" + maxShu(arr));
    }
 
    private static int max(int[] arr, int index) {
        if (index <s 1) {
            return 0;
        }
        if (index == 1) {
            return arr[0];
        }
        return Math.max(max(arr, index -1), max(arr, index - 2)+arr[index - 1]);
    }
 
    //最优子结构+地推公式+重叠子问题
    private static int maxMoney(int[] arr) {
        int length = arr.length;
        if (arr == null || length == 0) {
            return 0;
        }
        if (length == 1) {
            return arr[0];
        }
        int[] dp = new int[length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
//        dp[1] = arr[1];//注意,这里不能直接选择数组中第二个数据,当数据为arr2的情况时,会出现错误
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[length - 1];
    }
    private static int maxShu(int[] arr) {
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                sum1 += arr[i];
            } else {
                sum2 += arr[i];
            }
        }
        return Math.max(sum1, sum2);
    }

最大数为:17
最大数为:17
最大数为:17