查看: 695|回复: 4
收起左侧

刷题笔记七:动态规划‼️

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
刷题笔记七:动态规划

还是跟以前的笔记一样,总结参考了作者高畅的LeetCode101, 题目都是来自leetcode, 题解用的语言是python!
核心:这里我们引用一下维基百科的描述:“动态规划(Dynamic Programming, DP)在查找有很多 重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问 题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划 保存递归时的结果,因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优 子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能 完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。” 通俗一点来讲,动态规划和其它遍历算法(如深/广度优先搜索)都是将原问题拆成多个子问 题然后求解,他们之间最本质的区别是,动态规划保存子问题的解,避免重复计算。解决动态规 划问题的关键是找到状态转移方程,这样我们可以通过计算和储存子问题的解来求解最终问题。 同时,我们也可以对动态规划进行空间压缩,起到节省空间消耗的效果。这一技巧笔者将在 之后的题目中介绍。 在一些情况下,动态规划可以看成是带有状态记录(memoization)的优先搜索。状态记录的 意思为,如果一个子问题在优先搜索时已经计算过一次,我们可以把它的结果储存下来,之后遍 历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的,即先解决子问题,再解 决父问题;而用带有状态记录的优先搜索是自上而下的,即从父问题搜索到子问题,若重复搜索 到同一个子问题则进行状态记录,防止重复计算。如果题目需求的是最终状态,那么使用动态搜 索比较方便;如果题目需要输出所有的路径,那么使用带有状态记录的优先搜索会比较方便。
举例:
LC 70. Climbing Stairs (Easy): 给定 n 节台阶,每次可以走一步或走两步,求一共有多少种方式可以走完这些台阶。
题析: 这是十分经典的斐波那契数列题。定义一个数组 dp,dp 表示走到第 i 阶的方法数。因为 我们每次可以走一步或者两步,所以第 i 阶可以从第 i-1 或 i-2 阶到达。换句话说,走到第 i 阶的 方法数即为走到第 i-1 阶的方法数加上走到第 i-2 阶的方法数。这样我们就得到了状态转移方程 dp = dp[i-1] + dp[i-2]。注意边界条件的处理。
题解:请看图。
Screen Shot 2022-06-19 at 9.16.57 PM.png


Lc 198. House Robbe: 假如你是一个劫匪,并且决定抢劫一条街上的房子,每个房子内的钱财数量各不相同。如果 你抢了两栋相邻的房子,则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。
题析:定义一个数组 dp,dp 表示抢劫到第 i 个房子时,可以抢劫的最大数量。我们考虑 dp, 此时可以抢劫的最大数量有两种可能,一种是我们选择不抢劫这个房子,此时累计的金额即为 dp[i-1];另一种是我们选择抢劫这个房子,那么此前累计的最大金额只能是 dp[i-2],因为我们不 能够抢劫第 i-1 个房子,否则会触发警报机关。因此本题的状态转移方程为 dp = max(dp[i-1], nums[i-1] + dp[i-2])。
题解:请看图。
Screen Shot 2022-06-19 at 9.17.45 PM.png


LC413 Arithmetic Slices: 给定一个数组,求这个数组中连续且等差的子数组一共有多少个。
题析:这道题略微特殊,因为要求是等差数列,可以很自然的想到子数组必定满足num-num[i-1] = num[i-1] - num[i-2]。然而由于我们对于 dp 数组的定义通常为以 i 结尾的,满足某些条件的子数 组数量,而等差子数组可以在任意一个位置终结,因此此题在最后需要对 dp 数组求和。
题解:请看图。
Screen Shot 2022-06-19 at 9.18.19 PM.png


练习题:Lc 64. Mininum Path Sum
Screen Shot 2022-06-19 at 9.19.26 PM.png



求加米~








image.png

上一篇:有没有java刷题小群,不超过十个人的那种
下一篇:大龄宝妈0基础转码求组队!
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
lz棒棒!
回复

使用道具 举报

 楼主| 微信用户_9c1385b 2022-6-20 11:45:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎

哈哈,谢谢,咱们一起加油!
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (32)
 
 
11% (4)    👎
lz能认识一下吗 我邮箱leiyaouwm@gmail.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表