题目地址

  • 🙂 第一次练习 2020å¹´4月20日 这个题,自己之前在一年前做过,还是算比较巧妙的吧。
  • 😄 第二次练习

# 动态规划

因为题目是一个环状,所以此时会附加一个额外的条件,就是头尾不能同时打家劫舍,所以只需要判断偷第一家和不偷第一家的值,谁最大就好啦

解题代码

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]);
    }

    return Math.max(rec_rob(nums, 0), rec_rob(nums, 1));
}

public int rec_rob(int[] nums, int index) {
    int[] arr = new int[nums.length - 1];
    arr[0] = nums[index];
    arr[1] = Math.max(nums[index], nums[index + 1]);
    for (int i = 2; i < arr.length; i++) {
        arr[i] = Math.max(nums[index + i] + arr[i - 2], arr[i - 1]);
    }
    return arr[nums.length - 2];
}

# 易错点

  • 易错项 1
最后编辑时间: 4/20/2020, 10:50:02 AM