知识点

1. 知识点

   1. 打家劫舍问题

      1. 打家劫舍问题，是经典的一组动态规划问题。它主要有3个变种，这里我们就来讲一下这3个题。

      2. LeetCode题目

         • 198.【打家劫舍】

           解题思路：

           解决动态规划问题就是找「状态」和「选择」

           这个专业强盗，从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。

           如果抢了这间房子，那么你肯定不能抢相邻的下一间房子了，只能从下下间房子开始做选择。

           如果你不抢这间房子，那么你可以走到下一间房子前，继续做选择。

           当走过了最后一间房子后，就没得抢了，能抢到的钱显然是 0（base case）。

           以上的逻辑已经明确了「状态」和「选择」：面前房子的索引就是状态，抢和不抢就是选择。

           在两个选择中，每次都选更大的结果，最后得到的就是最多能抢到的 money。

           至此，穷举所有结果的回溯算法很容易就出来了：

           我们再使用一个dp数组，消除重叠子问题，自顶向下的动态规划算法就出来了：

           我们也可以直接利用状态和选择，找出状态转移方程和base case。base case就是，第一个房子能抢到的最大钱数就是第一个房子的钱数，第二个房子能抢到的最大钱数就是max(dp[0], dp[1])。状态转移方程为：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。因此自底而上的动态规划算法为：

             // 如果只有一间房子，说明最大能抢的钱数就是第一间的钱数
             if (nums.length == 1) return nums[0];
           
             int n = nums.length;
           
             // 定义dp数组
             int[] dp = new int[n];
           
             // base case
             dp[0] = nums[0];
             dp[1] = Math.max(nums[0], nums[1]);
           
             for (int i = 2; i < n; i++) {
                 dp[i]= Math.max(dp[i - 1], dp[i - 2] + nums[i]);
             }
           
             return dp[n - 1];

         • 213.【打家劫舍 II】

           解题思路：

           该题目，因为首尾的房子也看做是相邻的，因此首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢

           所以我们可以针对这三种情况，使用第一问的算法对它们各自求最大抢钱数，最后取三个情况中的最大值即可。

           算法如下：

             public int rob(int[] nums) {
           
                 if (nums.length == 1) return nums[0];
           
                 int res = -1;
           
                 // 只抢首个房子
                 res = Math.max(res, price(nums, 0, nums.length - 2));
           
                 // 只抢尾部房子
                 res = Math.max(res, price(nums, 1, nums.length - 1));
           
                 return res;
             }
           
             public int price(int[] nums, int start, int end) {
           
                 int n = end - start + 1;
           
                 if (n == 1) return nums[start];
           
                 // 定义dp数组
                 int[] dp = new int[n];
           
                 // base case
                 dp[0] = nums[start];
                 dp[1] = Math.max(nums[start], nums[start + 1]);
           
                 for (int i = 2; i < n; i++) {
                     dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
                 }
           
                 return dp[n - 1];
             }

LeetCode算法