第198题:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。来源:力扣(LeetCode)
1、当只有一间房屋时,最大金额就是这个房屋的钱;
如果有两间房屋,那么最大金额就是这两套房屋的里面的最大金额;
如果房屋大于两间的话,当有k间房子,我们需要计算这k间房子的最大金额;
那么它只能是前面k-2间房子的最大金额加上第k间房子的金额或者不偷第k间房子,直接等于前面k-1间房子的最大金额
利用dp数组来表示就是:dp[k]=max(dp[k-2]+nums[k] , dp[k-1]);
(也可以用自身这个数组来存储数据)
最终返回结果dp[nums.length-1]。
2、可以看出动态规划里面每次求存在k间房屋的最大金额时,这个最大金额之和它之前的k-1的最大金额和k-2的最大金额有关;
所以可以使用两个参数来代替dp数组,每次更改这两个参数最终得到结果。
第213题:
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。来源:力扣(LeetCode)
1、和上面的题一样,不能选择相邻的两间房屋,而且现在最后一间房子和第一间房子是相连的,说明这些房子是形成了一个环状;
因为最后一间和第一间是连起来的,所以这两者是不能同时选中的;
可以将这个问题分成两个子问题,求不选择最后一间房子的最大金额和不选择第一间房子的最大金额
然后得出最大的金额