全国新农村建设网站,外包和劳务派遣哪个好,网站怎么做关键字,泉州网站建设+推广力扣刷题11——打家劫舍1和2——[线性动态规划] 一、博客声明二、题目描述三、解题思路1、线性动态规划 a、什么是动态规划 2、思路说明 四、解题代码#xff08;附注释#xff09; 一、博客声明 找工作逃不过刷题#xff0c;为了更好的督促自己学习以及理解力扣大佬们的解… 力扣刷题11——打家劫舍1和2——[线性动态规划] 一、博客声明二、题目描述三、解题思路1、线性动态规划 a、什么是动态规划 2、思路说明 四、解题代码附注释 一、博客声明 找工作逃不过刷题为了更好的督促自己学习以及理解力扣大佬们的解题思路开辟这个系列来记录。代码可能不是自己写的不求方法最好只求更多地理解大佬们的解题思路。 二、题目描述 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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 100
0 nums[i] 400三、解题思路
1、线性动态规划 a、什么是动态规划 动态规划不是一种算法而是一种思想和解题策略。而要掌握动态规划比较难小编还没有掌握还在努力算题中。也不知道该怎么解释。推荐大家去看下面的视频 视频1【动态规划】这可能是最好懂的动态规划入门教程 视频2动态规划入门50题
2、思路说明 换种理解方式如果有A,B,C,D四个区域如何保证我穿过四个区域走的路程最长是不是就是只要保证每个区域都走最长的路就可以保证四个区域后我走的路程最长。 那么打家劫舍这个题目换个思想只要保证我到第i家时不管偷还是不偷手里积累的钱是两种策略偷和不偷中最多的就可以了。如果偷的话钱就变为偷到前前一家积累的钱加上这家的钱不偷的话就是偷到前一家积累的钱。比较这两个谁大就可以了。然后就是保存好偷到第i-2家和偷到第i-1家积累的钱方便对下一家是否偷作为判断依据。 1、如果数组长度等于1返回nums[0] 2、如果数组长度等于2返回fmax(nums[0], nums[1]) 3、如果数组长度大于2就需要从第三房子开始判断偷还是不偷这两种选择哪种选择能让当前手中积累的钱更多 打家劫舍2只需要考虑偷盗的范围就可以了代码最后一行变为return fmax(stealRang(nums, 0, numsSize - 2), stealRang(nums, 1, numsSize - 1));。也就是考虑第一家偷的话最后一家就不能偷范围就变为从第0家偷到numsSize-2家如果不偷第一家范围就变成了从第1家偷到第numsSize-1家比较这两个谁大就可以了。 四、解题代码附注释
///偷窃范围从第start家到第end家。
int stealRang(int* nums, int start, int end){int first nums[start], second fmax(first, nums[start1]);for(int i start 2; i end; i){int temp second;//考虑第i家偷与不偷哪个得的钱更多不偷就还是原来的second值偷就是前一家该家金额second fmax(second, first nums[i]);first temp;}return second;
}//该题目为属于线性动态规划题目
int rob(int* nums, int numsSize) {if(numsSize 1){//长度为1返回第一个元素return nums[0];}if(numsSize 2){//长度为2返回两个元素中最大的return fmax(nums[0], nums[1]);}return stealRang(nums, 0, numsSize - 1);//返回最大值//return fmax(stealRang(nums, 0, numsSize - 2), stealRang(nums, 1, numsSize - 1)); //打家劫舍2返回这个
}
