【LeeCode】198. 打家劫舍

【题目描述】

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

​​https://leetcode.cn/problems/house-robber/?favorite=2cktkvj​​

【示例】

【代码】​​官方​​

动态规划

package com.company;
// 2023-1-3

class Solution {
    public int rob(int[] nums) {
       int pre = 0;
       int cur = 0;

       for (int x : nums){
           int tmp = Math.max(cur, pre + x);
           pre = cur;
           cur = tmp;
       }
        return cur;
    }
}

public class Test{
    public static void main(String[] args) {
        int[] arr = {1,2,3,1};
        new Solution().rob(arr);       // 输出  4

        int[] arr2 = {2,7,9,3,1};
        new Solution().rob(arr2);      // 输出  12

        int[] arr3 = {2,1};
        new Solution().rob(arr3);      // 输出  2

        int[] arr4 = {1, 3, 1};
        new Solution().rob(arr4);      // 输出  3
    }
}

【代码】admin

通过率 40/70 遇到[2,1,1,2]的时候才发现真正理解题意了 这个输出是 4 而本代码输出3 

package com.company;
// 2023-1-3

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 max = 0;
        // {1, 3, 1}
        for (int i = 0; i < nums.length; i++){
            int sum = 0;
            for (int j = i; j < nums.length; j+= 2) {
                sum += nums[j];
            }
            max = Math.max(sum, max);
            max = Math.max(max, nums[i]);
        }
        System.out.println(max);
        return max;
    }
}

public class Test{
    public static void main(String[] args) {
        int[] arr = {1,2,3,1};
        new Solution().rob(arr);       // 输出  4

        int[] arr2 = {2,7,9,3,1};
        new Solution().rob(arr2);      // 输出  12

        int[] arr3 = {2,1};
        new Solution().rob(arr3);      // 输出  2

        int[] arr4 = {1, 3, 1};
        new Solution().rob(arr4);      // 输出  3
    }
}

package com.company;
// 2023-1-3

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 max = 0;
        // {1, 3, 1}
        for (int i = 0; i < nums.length; i++){
            int sum = 0;
            for (int j = i; j < nums.length; j+= 2) {
                sum += nums[j];
            }
            max = Math.max(sum, max);
            max = Math.max(max, nums[i]);
        }
        System.out.println(max);
        return max;
    }
}

public class Test{
    public static void main(String[] args) {
        int[] arr = {1,2,3,1};
        new Solution().rob(arr);       // 输出  4

        int[] arr2 = {2,7,9,3,1};
        new Solution().rob(arr2);      // 输出  12

        int[] arr3 = {2,1};
        new Solution().rob(arr3);      // 输出  2

        int[] arr4 = {1, 3, 1};
        new Solution().rob(arr4);      // 输出  3
    }
}