【动态规划入门】【1.2打家劫舍问题】【从记忆化搜索到递推】【灵神题单】【刷题笔记】

embedded/2024/11/29 2:38:44/

LeetCode 198. 打家劫舍

一、题目详情

题目难度:中等

题目描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。

二、示例演示

示例 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

从记忆化搜索到递推

启发思路:

  • 不选

DP新手三部曲:

  1. 思考回溯怎么写:
    • 入参和返回值
    • 递归到哪里
    • 递归边界和入口
  2. 改成记忆化搜索
  3. 1:1翻译成递推

打家劫舍,不能选相邻数字,使得数字加和最大

  • 从第一个房子或者最后一个房子开始思考最容易,因为受到制约最小
  • 比如,考虑最后一个房子选或者不选:
    • 如果不选,问题就变成了n-1 个房子
    • 如果选,问题就变成了n-2个房子的问题
    • 不断递归思考下去,得到一颗搜索树,每个分叉都是选不选

把刚才的思考过程抽象化:
回溯三问:

  1. 当前操作:枚举i个房子选不选
  2. 子问题:从i个房子中得到的最大金额和
  3. 下一个子问题:
    • 不选:从i-1个房子中得到的最大金额和
    • 选:从i-2个房子中得到的最大金额和
  • d f s ( i ) dfs(i) dfs(i)就表示从i个房子得到的最大金额和
  • 第和前: d f s ( i ) dfs(i) dfs(i),定义DFS或者DP数组时,只能表示从一些元素算出的结果,而不是一个元素算出来的!
  • 得到的金额没有当作入参,而是当成了返回值

回溯写法

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)def dfs(i): # i是房子编号if i < 0: # 没有房子可以偷了return 0 # dfs(i)表示前i个房子能取得的最大金额# dfs(i-1)表示,不选当前i# dfs(i-2) + nums[i]表示,选当前ires = max(dfs(i-1), dfs(i-2) + nums[i])return resreturn dfs(n-1)  #从最后一个开始!
__________
超时        

由于回溯的时间复杂度是指数级别的
优化思路:

  • 剪枝
  • res = max(dfs(i-1), dfs(i-2) + nums[i])里面递归调用dfs(i-1)和dfs(i-2)
  • 其实dfs(i-1)里面算过一次dfs(i-2)
  • 在第一次算时把结果保存下来,要用的时候直接调用
  • 把递归计算结果保存:下次递归到同样的入参时,就直接返回先前保存的结果
  • 时间复杂度优化到了 O ( n ) O(n) O(n)

递归搜索+保存计算结果=记忆化搜索

  • 对于python,要用到@cache ,原理是用一个hashmap记录下入参和对应的返回值
  • 对于这份代码可以用数组实现
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)cache = [-1] * ndef dfs(i): # i是房子编号if i < 0: # 没有房子可以偷了return 0 if cache[i] != -1:return cache[i]# dfs(i)表示前i个房子能取得的最大金额# dfs(i-1)表示,不选当前i# dfs(i-2) + nums[i]表示,选当前ires = max(dfs(i-1), dfs(i-2) + nums[i])cache[i] = resreturn resreturn dfs(n-1)  #从最后一个开始!
  • 复杂度 = 状态个数 O ( n ) O(n) O(n) * 单个状态所需要计算时间 O ( 1 ) O(1) O(1)

  • 空间复杂度也是 O ( n ) O(n) O(n)

  • 继续优化空间复杂度

  • 计算max发生在dfs调用结束后,也就是递归的归过程中。发生了实际计算

  • 干脆去掉递归中的递,只计算归的过程

  • 也就是自底向上算——递推(自顶向下——记忆化搜搜)

  • 1:1翻译成递推:(自下而上)

    • dfs ——> f 数组
      • dfs(i)=max(dfs(i-1), dfs(i-2)+nums[i])
      • ——>
      • f[i]=max(f[i-1], f[i-2]+nums[i])
      • 需要对i=0、1的情况特殊处理,因为会有特殊下标
      • 可以从i=2开始递推,避免出现负数下标
      • 也可以对每个下标+2
      • f[i+2]=max(f[i+1], f[i]+x)
    • 递归 ——> 循环
    • 递归边界 ——> 数组初始值
  • 但是这样写,会对i=0

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)f = [0] * (n+2) # 前两个位置空着,从i=2开始递推# 1:1翻译记忆化搜索res = max(dfs(i-1), dfs(i-2)+nums[i])for i, x in enumerate(nums):f[i+2] = max(f[i+1], f[i] + x)# 返回值应该是f的最后一个值!下标是n+1或者-1return f[-1]
  • 这份代码空间复杂度仍然是 O ( n ) O(n) O(n)
  • 如何修改,使其优化?
  • 关键递推公式:f[i+2] = max(f[i+1], f[i] + x)
  • 也可写作:f[i] = max(f[i-1], f[i-2] + nums[i])
  • f[i-1]上一个算的,f[i-2]上上个算出来的
  • 即要计算当前f[i],只需要直到上一个状态 f 1 f_1 f1和上上个状态的值 f 0 f_0 f0,实际上不需要记录所有状态!
  • n e w F = m a x ( f 1 , f 0 + n u m s [ i ] ) newF = max(f_1, f_0 + nums[i]) newF=max(f1,f0+nums[i])
  • 然后更新 f 1 f_1 f1= n e w F newF newF f 0 f_0 f0= f 1 f_1 f1
class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)# 初始化f0和f1都等于0f0 = f1 = 0for i, x in enumerate(nums):new_f = max(f1, f0 + x)f0 = f1f1 = new_freturn new_f #出了for循环new_f是局部变量,应该写f1!

740. 删除并获得点数

  • 选某个值val,记录,累加
  • 然后删掉所有val+1 val-1的值,不记录,这个值没了
  • 相当于选了某个值val,就选不了所有val+1-1的值,
  • 这是打家劫舍的影子吧

如何转换成打家劫舍?

  • 先统计出nums数组中每个数字出现的次数
  • 然后将每个数字与其出现次数乘积结果放入新数组对应位置
  • 问题就转化成了:新数组中,相邻元素不能同时选取,求出能获得的最大点数。
  • 也就是打家劫舍

这样问题就很简单了!一次就写出来了!

转换数组+打家劫舍+从记忆化搜索到递推
class Solution:def deleteAndEarn(self, nums: List[int]) -> int:new_nums = [0] * (max(nums) + 1)for i in range(len(nums)):new_nums[nums[i]] += nums[i]# 接下来就是打家劫舍问题!f0 = f1 =  0  # 初始化状态for i in range(len(new_nums)):new_f = max(f1, f0 + new_nums[i] )f0 = f1f1 = new_freturn f1
  • 注意这里new_nums长度应该是max(nums) + 1,一开始没+1是不对的!

2320.统计放置房子的方式数

以下是关于“2320. 统计放置房子的方式数”这道题的完整内容排版,包括代码、测试用例、测试结果示例,适合发布在CSDN等平台:

《LeetCode 2320. 统计放置房子的方式数 题解及示例》

一、题目详情

题目难度:中等

相关标签:[可填写具体相关算法标签,如“动态规划”等]

相关企业:[若知道常被哪些企业考察可填写]

题目描述:一条街道上共有 n ∗ 2 n * 2 n2 个地块,街道的两侧各有 n n n 个地块。每一边的地块都按从1到 n n n 编号。每个地块上都可以放置一所房子。现要求街道同一侧不能存在两所房子相邻的情况,请你计算并返回放置房屋的方式数目。由于答案可能很大,需要对 1 0 9 + 7 10^9 + 7 109+7 取余后再返回。注意,如果一所房子放置在这条街某一侧上的第 i i i 个地块,不影响在另一侧的第 i i i 个地块放置房子。

二、示例演示

示例1:
输入: n = 1 n = 1 n=1
输出: 4 4 4
解释:
可能的放置方式:

  1. 所有地块都不放置房子。
  2. 一所房子放在街道的某一侧。
  3. 一所房子放在街道的另一侧。
  4. 放置两所房子,街道两侧各放置一所。

三、解题思路

关键点分析

  • 本题有两个关键要点:一是街道同一侧不能存在两所房子相邻,这与经典的“打家劫舍”问题类似,都是相邻元素存在某种限制条件;
  • 二是街道两侧放置相互独立,互不影响,所以我们可以先单独考虑街道一侧的放置情况,然后再根据两侧独立的性质来计算总的放置方式数。

动态规划思路

  • 我们将问题转化为动态规划来解决。设 f [ i ] f[i] f[i] 表示在街道一侧前 i i i 个地块放置房子的方式数。
  • 递推公式推导
    • 对于 i i i 个地块,有两种情况:
      • 不放置房子在第 i i i 个地块,那么此时前 i i i 个地块放置房子的方式数就等于前 i − 1 i - 1 i1 个地块放置房子的方式数,即 f [ i ] = f [ i − 1 ] f[i] = f[i - 1] f[i]=f[i1]
      • 放置房子在第 i i i 个地块,由于不能与第 i − 1 i - 1 i1 个地块的房子相邻,所以此时前 i i i 个地块放置房子的方式数就等于前 i − 2 i - 2 i2 个地块放置房子的方式数,即 f [ i ] = f [ i − 2 ] f[i] = f[i - 2] f[i]=f[i2]
    • 综合这两种情况,前 i i i 个地块放置房子的方式数就是这两种可能情况的和,所以递推公式为: f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i - 1] + f[i - 2] f[i]=f[i1]+f[i2]

初始化分析

  • i = 0 i = 0 i=0 时,第0个地块也就是还没有地块,此时有一种放置方式,就是什么都不做,所以 f [ 0 ] = 1 f[0] = 1 f[0]=1
  • i = 1 i = 1 i=1 时,第1个地块只有一个地块,那么有两种放置方式,要么放房子,要么不放房子,所以 f [ 1 ] = 2 f[1] = 2 f[1]=2
  • 真的要被 ** **搞晕了!!!记得从i的定义出发,去思考如何初始化状态!

四、代码实现(Python)

递推版
class Solution:def countHousePlacements(self, n):mod = 10**9 + 7f = [1, 2]for i in range(2, n + 1):f.append((f[i - 1] + f[i - 2]) % mod)return (f[n] * f[n]) % mod

优化空间版

class Solution:def countHousePlacements(self, n: int) -> int:mod = 10 ** 9 + 7# fi表示第i个地块的放置方法# f0表示没有地块,什么也不做 也是一种方案f0 = 1# f1表示有一个地块,可以放或不放,结合f0f1 = 2# 单独看一侧,有n个地块,i=0和1的情况已经解决,从2开始递归# 递归到i=n,表示n个地块的方案才对for i in range(2, n+1): # 从0开始遍历?遍历到n-1?# new_f = f0 + f1# 更新f0为上上步f0 = f1# 更新f1为上步f1 = new_freturn f1 ** 2 % mod

在上述代码中:

  • 首先定义了一个常量 mod,用于对结果取余,以满足题目要求。
  • 初始化了列表 f,其中 f[0] 设为 1f[1] 设为 2,这是根据前面分析的初始化条件来设置的。
  • 然后通过循环,根据递推公式 f[i] = f[i - 1] + f[i - 2] 计算 f 列表中每个位置的值,并对结果取余。
  • 最后,由于街道两侧放置相互独立,所以总的放置方式数是街道一侧放置方式数的平方,返回 (f[n] * f[n]) % mod

很好,写出来了,继续打家劫舍!

打家劫舍II

  • 偷东西偷到土楼了!?
  • 偷看了一眼评论区,关键思路是直接分类讨论[0, n-2] 和[1, n-1]两种情况,手动隔离了首尾相连的难题!然后对比两种情况即可?
class Solution:def rob(self, nums: List[int]) -> int:# 打家劫舍递推公式:f[i]=max(f[i-1],f[i-2]+nums[i])n = len(nums)        # 特解,n小于4?if n < 4:return max(nums)        # 分类讨论[0, n-2] 和[1, n-1]两种情况f0 = nums[0]f1 = nums[1]# f2 = nums[2]# [0, n-2],i从2开始for i in range(2, n-1):new0_f = max(f1, f0 + nums[i])f0 = f1f1 = new0_f# [1, n-1], i从3开始f11 = nums[1]f22 = nums[2]for i in range(3, n):new1_f = max(f22, f11 + nums[i])f11 = f22f22 = new1_freturn max(f1, f22)
——————————————————————————————————————
解答错误
71 / 75 个通过的测试用例官方题解
输入
nums =
[1,3,1,3,100]添加到测试用例
输出
101
预期结果
103
————————————————————————————————————————————
改为:        f22 = max(nums[2], nums[1])后
————————————————————————————————————————————
解答错误
73 / 75 个通过的测试用例
  • 问题出在哪了?
  • 以上代码思路是:通过分类讨论,分别计算不包含最后一个房屋[0, n - 2]和不包含第一个房屋[1, n-1]这两种情况下能够偷窃到的最高金额,然后取两次结果最大值作为最终答案
  • 另一种思路是;
    • 定义辅助函数rob1:解决普通的打家劫舍问题
    • 调用rob1,分别计算nums[2:-1] + nums[0](即选了第一个房屋nums[0],相当于考虑了第一个房屋,但是不考虑最后一个房屋的中间部分)nums[1:](即不包含第一个房屋的情况)
class Solution:# 198. 打家劫舍def rob1(self, nums: List[int]) -> int:f0 = f1 = 0for x in nums:f0, f1 = f1, max(f1, f0 + x)return f1def rob(self, nums: List[int]) -> int:return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))作者:灵茶山艾府
链接:https://leetcode.cn/problems/house-robber-ii/solutions/2445622/jian-ji-xie-fa-zhi-jie-diao-yong-198-ti-qhvri/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

http://www.ppmy.cn/embedded/141325.html

相关文章

PICO VR串流调试Unity程序

在平时写Unity的VR程序的时候&#xff0c;需要调试自己写的代码&#xff0c;但是有的时候会发现场景过于复杂&#xff0c;不是HMD一体机能运行的&#xff0c;或者为了能够更方便的调试&#xff0c;不需要每次都将程序部署到眼睛里&#xff0c;这样非常浪费时间&#xff0c;对于…

区块链学习笔记(1)--区块、链和共识 区块链技术入门

常见的hash算法&#xff1a; 文件防篡改&#xff1a;MD5比特币挖矿&#xff1a;SHA256证明数据片段&#xff1a;Merkle root文本去重&#xff1a;SimHash 区块 区块&#xff08;block&#xff09;由区块头&#xff08;block header&#xff09;和交易列表&#xff08;transac…

Redis1——基本命令及原理

文章目录 Redis1——基本命令及原理1. Redis原理1.1 特点1.2 数据类型及其存储方式1.2.1 **string** 字符串1.2.2 **list** 列表1.2.3 **hash** 哈希表1.2.4 **set** 集合1.2.5 **zset** 有序集合 2. 基本命令及应用场景&#xff1a;2.1 Redis应用场景2.2 string——sds动态字符…

Fink的安装与入门

finl是做流式计算的大数据工具 官网&#xff1a;Apache Flink Documentation | Apache Flink Flink官方提供了Java、Scala、Python语言接口用以开发Flink应用程序 Fink的应用场景&#xff1a; Standalone集群模式安装部署 Flink支持多种安装模式。 local&#xff08;本地&am…

电子电气架构 --- 企业级别的诊断需求规范应该有哪些?

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…

如何使用docker启动一个gitlab

1. 下载ce版本镜像 gitlab/gitlab-ce:17.3.6-ce.0 2. 创建相关目录 /home/lylgitlab/config/home/lylgitlab/logs/home/lylgitlab/data/home/lylgitlab/other/gitlab.rb/home/lylgitlab/other/shm 3. 启动镜像 #!/bin/shdocker run --detach \--hostname 20.198.40.20 \-p …

Windows下的Milvus安装-保姆级安装教程

文章目录 一、简介二、dockers的安装1. 环境准备2.启动WSL 的功能。4.Docker的安装5.验证是否安装成功三、安装Milvus1.Milvus下载2.Milvus启动与验证四、Milvus图形化界面attu安装1、attu下载2、attu安装一、简介 Milvus是一个高性能、高度可扩展的矢量数据库,可在从笔记本电…

15分钟做完一个小程序,腾讯这个工具有点东西

我记得很久之前&#xff0c;我们都在讲什么低代码/无代码平台&#xff0c;这个概念很久了&#xff0c;但是&#xff0c;一直没有很好的落地&#xff0c;整体的效果也不算好。 自从去年 ChatGPT 这类大模型大火以来&#xff0c;各大科技公司也都推出了很多 AI 代码助手&#xff…