你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,使用javascript计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
时间: 2023-05-17 13:07:38 浏览: 240
可以使用动态规划来解决这个问题。假设我们已经计算出了前i-1个房屋能够偷窃到的最高金额,那么对于第i个房屋,我们有两种选择:偷或不偷。如果我们选择偷第i个房屋,那么前i-2个房屋一定不能偷,因为如果偷了相邻的房屋,就会触发警报。因此,偷第i个房屋能够得到的最高金额就是前i-2个房屋能够偷窃到的最高金额加上第i个房屋中的现金。如果我们选择不偷第i个房屋,那么前i-1个房屋能够偷窃到的最高金额就是前i-1个房屋能够偷窃到的最高金额。因此,我们可以得到如下的状态转移方程:
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
其中,dp[i]表示前i个房屋能够偷窃到的最高金额,nums[i]表示第i个房屋中的现金。
最终的答案就是dp[nums.length-1],即前nums.length个房屋能够偷窃到的最高金额。以下是完整的javascript代码:
function rob(nums) {
if (nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
let dp = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
console.log(rob([1,2,3,1])); // 4
console.log(rob([2,7,9,3,1])); // 12
阅读全文