北京企业网站开发,优秀网站推荐,山西省建设部网站,注册网站费属于什么费用原题链接#xff1a;
198. 打家劫舍 题目描述#xff1a;
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入
198. 打家劫舍 题目描述
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
数据范围
1 nums.length 1000 nums[i] 400
测试样例
示例 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 。思路二维动态规划
对于每一家而言都有 偷了 和 没偷 这两种状态所以可以用一个二维 dp 数组共 2 行 n 列来表示某一家是否被偷。顺序遍历原数组模拟小偷从第一家偷到最后一家的过程。那么有 dp[0][i] 表示小偷走到索引为 i 的那一家但是没偷他们家时获得的最大金额相应的 dp[1][i] 表示小偷走到索引为 i 的那一家并且偷了他们家时获得的最大金额。因为被偷的两家不能相邻所以可以得到递推关系dp[0][i] max(dp[0][i-1], dp[1][i-1])因为 dp[0][i] 表示没有偷这一家所以偷没偷前面的一家无所谓返回二者中的最大值dp[1][i] dp[0][i-1] nums[i]因为 dp[1][i] 表示偷了这一家所以前一家必定不能偷只能是 dp[0][i-1] 但是又因为偷了当前这个一家收益还要增加 nums[i]。并且可以得到初始值分别为 dp[0][0] 0 和 dp[1][0] nums[0]。仔细思考一下发现不重复不遗漏那么最终的结果就是小偷走到最后一家时的最大收益 max(dp[0][n-1], dp[1][n-1])。 代码
class Solution {
public:int rob(vectorint nums) {int n nums.size();int dp[2][n];dp[0][0] 0, dp[1][0] nums[0];for (int i 1; i n; i ) {dp[0][i] max(dp[0][i-1], dp[1][i-1]);dp[1][i] dp[0][i-1] nums[i];}return max(dp[0][n-1], dp[1][n-1]);}
}; 复杂度
时间复杂度
遍历了一遍整个数组
时间复杂度为 O(N) 空间复杂度
创建了一个辅助数组存储 dp 结果
空间复杂度为 O(N)
