兴文县建设工程网站,3000行业关键词,网站 猜你喜欢 怎么做,企业网站发布图片文章目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
198. 打家劫舍 - 力扣#xff08;LeetCode#xff09; 题目描述
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装…目录
题目来源
题目描述
示例
提示
题目解析
算法源码 题目来源
198. 打家劫舍 - 力扣LeetCode 题目描述
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例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 。提示
1 nums.length 1000 nums[i] 400题目解析
如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
因此小偷如果偷了第 i 间那么必然不能偷第 i 1间可以选择偷或不偷第 i 2间。
上面这种后发状态取决于前面状态的很容易就想到使用动态规划来求解。 我们定义一个dp数组dp[i] 的含义是在 0 ~ i 间屋子中偷盗小偷所能获得的最大金额。
对于第 i 间屋子小偷有两种选择偷、或者不偷如果
小偷选择偷第 i 间屋子那么小偷可以获得nums[i]的金额但是必然不能再偷第 i - 1 间屋子了而接下来就变为了偷或不偷第 i - 2间屋子即有转移方程 dp[i] dp[i-2] nums[i]小偷选择不偷第 i 间屋子那么小偷此时无法获得第 i 间屋子的金额接下来就变为偷或不偷第 i - 1间屋子即有转移方程 dp[i] dp[i-1]
我们只要在上面两个状态中选择最大的即可 dp[ i ] max( dp[ i - 1 ], dp[ i - 2 ] nums[ i ] ) Java算法源码
class Solution {public int rob(int[] nums) {int n nums.length;int[] dp new int[n];dp[0] nums[0];if(n 1) return dp[0];dp[1] Math.max(nums[0], nums[1]);if(n 2) return dp[1];for(int i2; in; i) {dp[i] Math.max(dp[i-1], dp[i-2] nums[i]);}return dp[n-1];}
} JavaScript算法源码
/*** param {number[]} nums* return {number}*/
var rob function(nums) {const n nums.lengthconst dp new Array(n).fill(0)dp[0] nums[0]if(n 1) return dp[0]dp[1] Math.max(nums[0], nums[1])if(n 2) return dp[1]for(let i2; in; i) {dp[i] Math.max(dp[i-1], dp[i-2] nums[i])}return dp[n-1]
}; Python算法源码
class Solution(object):def rob(self, nums):n len(nums)dp [0]*ndp[0] nums[0]if n 1:return dp[0]dp[1] max(nums[0], nums[1])if n 2:return dp[1]for i in range(2, n):dp[i] max(dp[i-1], dp[i-2] nums[i])return dp[n-1]
