当前位置: 首页> 科技> 名企 > 深汕特别合作区面积_手机网页wap_全网推广_站长工具ip地址查询

深汕特别合作区面积_手机网页wap_全网推广_站长工具ip地址查询

时间:2025/7/11 1:08:07来源:https://blog.csdn.net/qq_57349657/article/details/144352915 浏览次数:2次
深汕特别合作区面积_手机网页wap_全网推广_站长工具ip地址查询

题目

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

思路

一、递归搜索 + 保存计算结果 = 记忆化搜索

二、1:1翻译成递推

三、空间优化

代码

class Solution {  // 一、递归搜索 + 保存计算结果 = 记忆化搜索private int[] nums,memo;public int rob(int[] nums) {this.nums = nums;int n = nums.length;memo = new int[n];Arrays.fill(memo,-1); // -1表示没有计算过return dfs(n-1);}private int dfs(int i){if (i < 0)  // 递归边界return 0;if(memo[i] != -1) // 之前计算过return memo[i];int res = Math.max(dfs(i-1),dfs(i-2)+nums[i]);memo[i] = res; // 记忆化:保存计算结果return res;}
}
class Solution {  // 二、1:1翻译成递推public int rob(int[] nums) {int n = nums.length;int[] f = new int[n + 2];for (int i = 0; i < n; i++) {f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);}return f[n + 1];}
}

:为什么只需要把 f 的下标 +2,nums 的下标不需要 +2?

:把 nums 的下标 +2 是错误的。第一,nums[0] 和 nums[1] 要怎么算进答案中呢?第二,当 i=n−1 时,i+2=n+1,这会导致 nums 数组越界。

class Solution {  // 三、空间优化public int rob(int[] nums) {int f0 = 0;int f1 = 0;for (int x : nums) {int newF = Math.max(f1, f0 + x);f0 = f1;f1 = newF;}return f1;}
}

性能

空间优化: 时间o(n)   空间o(1)

关键字:深汕特别合作区面积_手机网页wap_全网推广_站长工具ip地址查询

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: