知识点
知识点
打家劫舍问题
打家劫舍问题,是经典的一组动态规划问题。它主要有3个变种,这里我们就来讲一下这3个题。
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]; }