题目链接
打家劫舍
题目描述
注意点
- 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警
- 0 <= nums[i] <= 400
解答思路
- 最初想的是使用深度优先遍历,到达任意一个位置时,小偷想要偷窃最高金额,一定要选择后面第2个房屋或后面第3个房屋,所以dfs遍历时根据后面第2个房屋和后面第3个房屋的金额判断当前位置的最高金额
- 使用dfs同一个房屋会被计算多次,当数据量变大时会超时,选择使用动态规划解决本题,其思想为:任意一个房屋的金额由其前面第2个房屋及前面第3个房屋的最高金额决定,所以只需要一次遍历就可不断推出后面房屋的最大金额
代码
class Solution {public int rob(int[] nums) {if (nums.length == 1) {return nums[0];}if (nums.length == 2) {return Math.max(nums[0], nums[1]);}int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];dp[1] = nums[1];dp[2] = nums[0] + nums[2];for (int i = 3; i < n; i++) {dp[i] = nums[i] + Math.max(dp[i - 2], dp[i - 3]);}return Math.max(dp[n - 1], dp[n - 2]);}
}
关键点
- 动态规划的思想