原题链接:
198. 打家劫舍
https://leetcode.cn/problems/house-robber/description/文章来源:https://www.toymoban.com/news/detail-807248.html
完成情况:
文章来源地址https://www.toymoban.com/news/detail-807248.html
参考代码:
_198打家劫舍
package 代码随想录.动态规划;
public class _198打家劫舍 {
/**
*
* @param nums
* @return
*/
public int rob(int[] nums) {
// TODO 每次偷窃后,必须至少冷却一天,问多大头去数量数多少
if(nums == null || nums.length == 0){
return 0;
}
if (nums.length == 1) {
return nums[0];
}
//有多个时,才需要使用到dp
int [] dp = new int[nums.length];
//模拟出取每一个长度位置时的最大累计和
dp[0] = nums[0];
dp[1] = Math.max(dp[0],nums[1]);
for (int i=2;i< nums.length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length - 1];
}
}
_198打家劫舍_滚动优化
package 代码随想录.动态规划;
public class _198打家劫舍_滚动优化 {
/**
* 进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
* @param nums
* @return
*/
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
//初始化dp数组
//优化空间,dp数组只用2个空间,只记录与当前计算相关的前两个结果
int [] dp = new int[2];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
int res = 0;
//遍历
for (int i=2;i< nums.length;i++){
res = Math.max((dp[0] + nums[i]),dp[1]);
dp[0] = dp[1];
dp[1] = res;
}
//输出结果
return dp[1];
}
}
_198打家劫舍_滚动数组
package 代码随想录.动态规划;
public class _198打家劫舍_滚动数组 {
/**
* 分析本题可以发现,所求结果仅依赖于前两种状态,此时可以使用滚动数组思想将空间复杂度降低为3个空间
* @param nums
* @return
*/
public int rob(int[] nums) {
int len = nums.length;
if (len == 0){
return 0;
} else if (len == 1) {
return nums[0];
}else if (len == 2){
return Math.max(nums[0],nums[1]);
}
//如果存在多个时。每次只看目之所及的三个
int result [] = new int[3]; //用来存放选择的结果
result[0] = nums[0];
result[1] = Math.max(nums[0],nums[1]);
//迭代遍历完整个数组
for (int i=2;i< len;i++){
result[2] = Math.max(result[0]+nums[i],result[1]);
result[0] = result[1];
result[1] = result[2];
}
return result[2];
}
}
错误经验吸取
到了这里,关于198. 打家劫舍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!