题目

image.png

思路

  • 思路一：暴力递归，由于不能连续偷窃，因此对于第i个房间有两种选择，偷与不偷，因此我们定义recur(int[] nums, int i)表示0到i中能偷窃的最大金额，其中递归分支是Math.max(recur(nums, i -2) + nums[i], recur(nums, i -1)，将问题分解成小问题，当i<0时就是递归终止条件
  • 思路二：备忘录
  • 思路三：动态规划，递归的逆过程，定义dp[i]表示0到i中能够窃取的最大金额，转移方程：dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])。初始状态：dp[0] = nums[0]，dp[1] = Math.max(nums[0],nums[1])
  • 思路四：优化dp数组的动态规划

代码

  1.     //1.暴力递归，超时
  2.     public int rob(int[] nums) {
  3.         return recur(nums, nums.length - 1);
  4.     }
  6.     public int recur(int[] nums, int i) {
  7.         if (i < 0) return 0;
  8.         return Math.max(recur(nums, i - 2) + nums[i], recur(nums, i - 1));
  9.     }
  11.      //2.备忘录，超时
  12.     int[] dp;
  13.     public int rob(int[] nums) {
  14.         dp = new int[nums.length];
  15.         return recur(nums, nums.length - 1);
  16.     }
  18.     public int recur(int[] nums, int i) {
  19.         if (i < 0) return 0;
  20.         if (dp[i] != 0) return dp[i];
  21.         dp[i] = Math.max(recur(nums, i - 2) + nums[i], recur(nums, i - 1));
  22.         return dp[i];
  23.     }
  25.     //3.动态规划
  26.     public int rob(int[] nums) {
  27.         if (nums.length == 0) return 0;
  28.         if (nums.length == 1) return nums[0];
  29.         int[] dp = new int[nums.length];
  30.         dp[0] = nums[0];
  31.         dp[1] = Math.max(nums[0],nums[1]);
  32.         for (int i = 2; i < nums.length; i++) {
  33.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  34.         }
  35.         return dp[nums.length - 1];
  36.     }
  38.     //4.优化dp数组的动态规划
  39.     public int rob(int[] nums) {
  40.         if (nums.length == 0) return 0;
  41.         if (nums.length == 1) return nums[0];
  42.         int p1 = nums[0], p2 = Math.max(nums[0],nums[1]), t = 0;
  43.         for (int i = 2; i < nums.length; i++) {
  44.             t = Math.max(p1 + nums[i], p2);
  45.             p1 = p2;
  46.             p2 = t;
  47.         }
  48.         return p2;
  49.     }

打家劫舍