个人觉得,学、思、练三者是相辅相成的关系,既然已经学习了动态规划,就拿力扣上的题来练下手吧! leetcode-cn.com/problems/ho…
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:
输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
思路分析:
针对每一个房屋,有2种选择:偷、不偷
如果现在有房子编号为0,1,2,3,4,5
如果偷第0号房子,sum1 = nums[0] + rob([2,3,4,5])
如果不偷第0号房子
sum2 = rob([1,2,3,4,5]) 偷到的最高金额应为二者中的最大值max(sum1,sum2)
思路一:递归(从前往后偷,从第一个偷或不偷开始)
var rob = function(nums) {
if(nums == null || nums.length == 0) return 0;
return robFn(nums,0);
};
function robFn(nums,begin){
// begin 是从0开始逐渐变大,加上这句,避免下标超过数组长度而越界,也是递归基。
if(begin == nums.length - 1) return nums[begin];
if(begin == nums.length - 2) return Math.max(nums[begin], nums[begin+1]);
let sum1 = nums[begin] + robFn(nums, begin+2) //偷begin
let sum2 = robFn(nums, begin+1) //不偷begin
return Math.max(sum1, sum2)
}
思路二:递归(从后往前偷,从最后一个偷或不偷开始)
var rob = function(nums) {
if (nums == null || nums.length == 0) return 0;
return robFn(nums, nums.length - 1);
};
function robFn(nums, begin) {
if (begin == 0) return nums[0];
if (begin == 1) return Math.max(nums[0], nums[1]) //避免下标成为负数而越界
let sum1 = nums[begin] + robFn(nums, begin - 2);//偷begin
let sum2 = robFn(nums, begin - 1);//不偷begin
return Math.max(sum1, sum2)
}
思路三:缓存(从后往前偷,从最后一个偷或不偷开始)
var rob = function(nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];//加上这句,nums至少有2个数据才会往下走,就不会报错了(NaN),这句一可以提高效率,二可以避免报错。
let arr = new Array(nums.length);//arr[begin]存放从begin开始往前偷的最大数
arr[0] = nums[0];
arr[1] = Math.max(nums[0], nums[1]);
for (let begin = 2; begin < nums.length; begin++){
arr[begin] = Math.max(nums[begin] + arr[begin - 2], arr[begin - 1]);
}
return arr[arr.length - 1]
};
思路四:优化从简复杂度,从O(n)到O(1)(从后往前偷,从最后一个偷或不偷开始)
var rob = function (nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];//加上这句,nums至少有2个数据才会往下走,就不会报错了(NaN),这句一可以提高效率,二可以避免报错。
let first = nums[0], second = Math.max(nums[0], nums[1]);
for (let begin = 2; begin < nums.length; begin++) {
let tmp = second;
second = Math.max(nums[begin] + first, second);
first = tmp;
}
return second;
};
再次优化
var rob = function (nums) {
if (nums == null) return 0;
let first = 0, second = 0;
for (let begin = 0; begin < nums.length; begin++) {
let tmp = second;
second = Math.max(nums[begin] + first, second);
first = tmp;
}
return second;
};
我的独创:空间复杂度0
var rob = function (nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length >= 2) nums[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
nums[i] = Math.max(nums[i] + nums[i - 2], nums[i - 1])
}
return nums[nums.length - 1]
};
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!