本文主要是介绍动态规划——打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：198. 打家劫舍，现去 i 个房间偷东西，每个房间能偷的价值一定，不能偷相邻的房间
测试函数：
public static void main(String[] args) {/*1 2 3 4 5 -->房间号0 0 0 0 01(2) 2 0 0 0 02(7) 2 7 0 0 03(9) 2 7 11 0 04(3) 2 7 11 11 05(1) 2 7 11 11 12举例：当 i = 4 时，即有 4 个房间可偷时，dp[4] = Max(11,3+7) = 11递推式：dp[i] = Max(dp[i-1],dp[i-2]+house[i])解释：上个房间时能偷的最大价值 与 (上上个房间时能偷的最大价值 + 当前房间的价值) ，求最大值则为有 i 个房间时能偷的最大价值*/// System.out.println(new HouseRobberL_198().rob1(new int[]{1, 2, 3, 1}));System.out.println(new HouseRobberL_198().rob(new int[]{2, 7, 9, 3, 1}));}实现函数：
/*** 不能偷相邻房间，求能偷到的最大价值** @param nums 索引：房间编号，值：该房间能偷到的价值* @return 能偷到的最大价值*/public int rob1(int[] nums) {int len = nums.length;if (len == 1) return nums[0];int[] dp = new int[len];//初始化 前两个房间的价值dp[0] = nums[0];dp[1] = Integer.max(nums[0], nums[1]);System.out.println(Arrays.toString(dp));for (int i = 2; i < len; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);System.out.println(Arrays.toString(dp));}return dp[len - 1];}将dp数组长度多一个 （即加上没有房间可偷的情况）
/*** 不能偷相邻房间，求能偷到的最大价值** @param nums 索引：房间编号，值：该房间能偷到的价值* @return 能偷到的最大价值*/public int rob(int[] nums) {int len = nums.length;if (len == 1) return nums[0];int[] dp = new int[len+1];//初始化 前两个房间的价值dp[1] = nums[0];System.out.println(Arrays.toString(dp));for (int i = 2; i < len+1; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i-1]);System.out.println(Arrays.toString(dp));}
/*0 1 2 3 4 5 -->房间号0 0 0 0 0 01(2) 0 2 0 0 0 02(7) 0 2 7 0 0 03(9) 0 2 7 11 0 04(3) 0 2 7 11 11 05(1) 0 2 7 11 11 12*/return dp[len];}这篇关于动态规划——打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
