代码随想录一刷笔记_动态规划(下)

60+在408的算法考察难度和深度上还是收手了👍)

198 打家劫舍

因为之前做了一周的背包问题,所以现在看到题目的第一反应就是,这是背包😖😖….

实际上这一题并不满足背包的条件,背包需要满足容量是固定的,但是这一题是让我求最大的容量,根据题设,这是一个小于40000的正整数….

213 打家劫舍Ⅱ

我的想法,本题和上一题的区别在于数组由线性的变成了环状的,所以我加了一个布尔类型的数组用于判断当前的最大值里有没有包含首位数字,然后最后进行一个判断。但是在[2,1,2,6,1,8,10,10]这个样例里面没有通过。

1
2
3
4
5
6
7
8
// 处理代码段
if (nums.size() >= 3) {
int delta1 = dp[nums.size() - 2] + nums[nums.size() - 1];
int delta2 = dp[nums.size() - 3] + nums[nums.size() - 1];
if (jud[nums.size() - 2]) delta1 -= min(nums[0], nums[nums.size() - 1]);
if (jud[nums.size() - 3]) delta2 -= min(nums[0], nums[nums.size() - 1]);
dp[nums.size()] = max(delta1, delta2);
}

题解

看了题解,我是想把这一部分在一个循环里实现,搞复杂了,实际上只要遍历两次dp数组(分别包含首元素和尾元素),然后取最大值即可。。。。

数组环的三种情况:

  1. 情况一:考虑不包含首尾元素
  2. 情况二:考虑包含首元素,不包含尾元素
  3. 情况三:考虑包含尾元素,不包含首元素

这里的情况一是包含在二和三里的,所以只需要遍历两遍取极大值即可。

PS:网友抚平了我提交10多次没有ac的痛苦,笑死了。

image-20241210145220476

337 打家劫舍Ⅲ

第一个想法是,遍历二叉树成一个用前/中/后序排序的数组,然后根据这个数组进行下一步操作,但是演算了一番,似乎不太行得通。

于是乎,就有了第二个想法,使用层序遍历,遍历二叉树成一个二维向量组呢?好像也不太行,只能解决根节点这一层和第二、三层的关系,后面的对应关系就不好找了。

好像还是得在遍历的过程中完成打劫(bushi)

记忆化递归

可以料到,如果使用递归的话大概率是会在一些样例上超时的,所以得要采取一点剪枝策略。

这里就引入了记忆化递归的方法。

使用一个map把计算过的结果保存一下,当重复遍历到一个节点时,可以直接复用结果,避免了重复遍历。

dp

卡哥定义这里的dp方法为树形dp(亦称为“树形贪心”),但还是逃不出dp五部曲的分析范围!

  1. 确定dp数组以及下标的含义

    这里的dp数组容量为2,表示当前偷 & 不偷。

  2. 确定递推公式

    数据存储在二叉树中,所以是要在遍历二叉树的过程中进行动规的!

    对当前节点root(dp[0]表示不偷,dp[1]表示偷):

    • 如果不偷这个节点

      1
      int val1 = max(left[0], left[1]) + max(right[0], right[1]);
    • 如果偷这个节点

      1
      int val2 = root->val + dp[0] + dp[1];

    显然,在计算root节点可以偷到的最大金额时,需要知道root的两个孩子节点的情况!故,这里需要采用后序遍历的方法递归二叉树!

  3. 递归函数如何初始化

    因为是使用后序遍历,所以只需在遍历到二叉树底部时初始化大小为0,容量为2的数组即可。

  4. 确定遍历顺序

    由上述可得,使用后序遍历二叉树的方法!

至此,打家劫舍完结力★,°:.☆( ̄▽ ̄)/$:.°★

121 买卖股票的最佳时机

试了下双重循环,超时咯!

贪心

简化成了单重循环,记录遍历到当前下标前的所有数值的最小值,然后进行一个比较。

dp

第一时间没想到怎么做👉👈

看了下答案,哦,需要使用二维数组啊。然后dp数组的长度就是买卖股票天数的长度,原谅我看到天数定义小于等于10^5的时候不想往这方面考虑了👉👈👉👈

  1. 数组下标及其含义

    dp[i][0]表示当天持有股票所得最多现金(是个负数,越大越好)

    dp[i][1]表示当天不持有股票所得最多现金(是个正数,越大越好)

  2. 确定递推公式

    • 对于持有股票

      1
      dp[i][0] = max(-prices[i], dp[i - 1][0]);
    • 对于不持有股票

      1
      dp[i][i] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
  3. 如何初始化

    其他都初始化为0,但是我们需要单独考虑一下第一天的情况(因为第一天没有前一天,比较特殊)。

122买卖股票的最佳时机Ⅱ

贪心

简单回顾一下使用贪心的做法,遍历整个数组,当当天的股价大于前一天的股价时,买入前一天的股票并在当天卖出(实际上是不可能的),达到局部最优的目的。

dp

与上题类似,还是分为买/不买的二维数组。

  1. 数组下标及其含义

  2. 递推公式

    • 对于买入股票(最多只能持有一股,所以在买入的时候得卖掉)

      考虑当天买入新股票和前些天买入新股票谁亏的少?

      1
      dp[i][0] = max(-prices[i] + dp[i - 1][1], dp[i - 1][0]);
      • 因为可以多次购买,所以需要考虑前面的收益有没有算进去的情况。只能同时购买一股,所以前一天不买入新股票的情况就是当天操作前的最佳收益,这样就算上了之前的操盘(凌乱的理解)。
    • 对于不买入股票

      考虑当天卖出股票和前些天卖出股票谁赚的多?

      1
      dp[i][1] = max(prices[i] + dp[i - 1][0], dp[i - 1][1]);

123 买卖股票的最佳时机Ⅲ

贪心(感觉应该是贪心?)

不难发现,可以把股价分成n个递增序列,然后我们要将他们合成两个差值是最大的,再求和。(不好实现)

聪明的claude给出了一个新思路。

  • 对于每一天,计算
    • 在这一天之前完成一次交易能获得的最大利润
    • 在这一天之后完成一次交易能获得的最大利润
  • 在所有可能的“分割点”中,找到左右两遍利润之和最大的情况

粗浅的理解一下,分割两边,是因为防止出现重复购买的情况!tql!我的超人claude老师!好大的脑洞!

dp

看了视频后,大彻大悟了属于是,卡哥牛逼!~

按照dp五部曲捋一下这一题。

  1. dp数组以及下标表示的含义

    这里的买卖股票规矩是至多买两次。将dp数组分为五行,分别表示没有操作过第一次持有(包含当天买入 & 前一天买入)第一次不持有(卖出力)第二次持有第二次不持有

  2. 递推公式

    按五种情况分别描述:

    • 没有操作过:畏惧炒股市场,所以一直是0(bushi)

    • 第一次持有,保留最便宜的一支股票

      1
      dp[1][i] = max(dp[0][i - 1] - prices[i], dp[1][i - 1]);
    • 第一次不持有,保留最赚的一次买卖经历

      1
      dp[2][i] = max(dp[1][i - 1] + prices[i], dp[2][i - 1]);
    • 第二次持有,在第一次的基础上操作

      1
      dp[3][i] = max(dp[2][i - 1] - prices[i], dp[3][i - 1]);
    • 第二次不持有,在第二次持有的基础上赚最多

      1
      dp[4][i] = max(dp[3][i - 1] + prices[i], dp[4][i - 1]);
  3. 初始化

    理解的方法:虽然说不能同时参与多笔交易,但是我们可以在同一天重复“买入-卖出-买入-卖出”的神金操作。

    1
    2
    3
    4
    5
    dp[0][0] = 0;
    dp[1][0] = -prices[0];
    dp[2][0] = 0;
    dp[3][0] = -prices[0];
    dp[4][0] = 0;123 买卖股票的最佳时机Ⅲ

188 买卖股票的最佳时机Ⅳ

相比123 买卖股票的最佳时机Ⅲ,这一题就差在可以交易k次上,把交易次数抽象了,但是思路还是一样滴!

309 买卖股票的最佳时机含冷冻期

显然,这一题是要在121 买卖股票的最佳时机上附加一个“冷冻期”概念的判定。在某一天不持有(卖出这股)后,后一天不能买进。第一个想法是,遍历过去,找到收入最高的一天(也就是找到差值最大的两天),这一天的后一天判定为冷冻期。

但是!好像最赚的方法还是多操作几次(有点贪心的意思,见好就收,不贪大钱)。

dbq,是我想太简单了ToT(好的,先去把前面两道炒股困难题啃了ヾ( ̄▽ ̄))

啃完了回来发现还是不会做,你管这叫中等题嘛,明明比前面的两道困难提难呀ToT()

  1. dp数组的下标及其含义

    可以细分为4个状态

    • 状态0:持股
    • 状态1:保持卖出的状态(不包含状态2和3)
    • 状态2:当天卖出
    • 状态3:冷冻期
  2. 递推公式

    • 状态0,可以保持前一天持股(状态0),保持卖出后持股(状态1),以及冷冻期过后持股(状态3)

      1
      dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
    • 状态1,可以是保持上一天卖出的状态(状态1),也可以是冷冻期后的状态(状态3)

      1
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
    • 状态2,来自持股后卖出(状态0)

      1
      dp[i][2] = dp[i - 1][0] + prices[i];
    • 状态3,来自卖出后(状态2)

      1
      dp[i][3] = dp[i - 1][2];

allinall,这一题麻烦在如何划分状态。状态1-3都是属于不持股,如何划分区分冷冻期与冷冻期过后很关键(好难想到。

714 买卖股票的最佳时机含手续费

最后一天的炒股之路竟然这么简单嘛()

dp

就是在122买卖股票的最佳时机Ⅱ的基础上每次卖出股票后添加一个交小费的操作(递推公式稍微改进一下)

贪心

不要考虑多次交易会导致小费交很多的问题。在做贪心的时候,首当其冲的就是要找局部最优解。

说到局部最优解,那还是和122买卖股票的最佳时机Ⅱ一样,局部最优解就是找到一个区间里的最小值和最大值(实际上这时候交易的次数就是最少的,焦虑的问题顺带解决了!)

300 最长递增子序列

回溯

题目的数组长度是小于等于2500,不回溯了==+

dp

按照dp五部曲分析一下(实际上感觉应该674 最长连续递增序列的次序交换一下,算法的遍历过程是相通的,而674很容易就能想到)。

  1. dp数组的下标及含义

    表示当前数字处于自己子序列中的最大位置

  2. dp的推导公式

    遍历到当前位置时,查找这个位置前面所有的比这个数小的节点,然后找到最长的序列。也就是说,我们不用管具体的序列是哪一串。

  3. 初始化

    初始化为1即可,即当前最长子序列长度为1。

674 最长连续递增序列

贪心

遍历一遍数组,局部最优就是最长的连续递增序列,时间复杂度为O(1)。

dp

dp数组下标记录的是当前数字在当前子序列中的排列,然后需要在dp数组中找到最大的记录。

718 最长重复子数组

我的做法(dp)

按照dp五部曲叙述一下

  1. dp数组的下标及其含义

    我定义dp数组的长度与nums1的长度相同,表示以当前字符为起点的最长重复子数组长度。

  2. 递推公式

    在另一个数组中找到与当前字符相同的字符位置,然后向后遍历,记录下最长重复子数组的长度。

  3. 初始化

    数组初始化为0即可,因为可能会出现当前数字在另一个数组中没有出现的情况。

时间复杂度为O(n^2)

题解(dp)

大体思路果然没有问题,想要降低时间复杂度,就只能考虑用空间换时间的方法了。

1143 最长公共子序列

我的做法(dp)

  1. dp数组的下标及其含义

    dp数组的长度为text1.size(),表示当前最长公共子序列的长度

  2. 递推公式

    两层循环嵌套遍历text1text2的每一个字符,然后当发现有相同字符的时候向前遍历找到当前最大的数组下标,当前表示数值就为此下标+1。

问题出在字符串中可能会出现重复的字符,我该如何保证在单次遍历中不会重复添加呢?然后我使用了vector向量用来存储已经遍历过的字符串部分,但是遇到了一个长度分别为210和240的字符串,在双重循环的情况下我还在这个循环里进行了一个查找的操作,好像溢出了。。。。

题解(dp)

还是得空间换时间,使用二维数组啊。。。。

1035 不相交的线

这一题做的挺懵的,虽然ac了,但是不知道具体的原理。

还得是carl哥,一语道破梦中人,仔细观察结果,可以发现,这里所得的序列就是1143 最长公共子序列的结果!

53 最大子数组和

使用一维数组作为dp数组,然后递推公式为在当前数值和与之前数值相加的和中取最大值。

392 判断子序列

使用了二维数组(在两个字符串分别为行和列的情况下又在顶部和左侧加了一行,为了方便计算第一行和第一列的情况)。这里需要注意的是,dp数组中对应到字符串中具体字符时是“-1”!!

115 不同的子序列

这一题的递推公式没有推出来👉👈

题解的做法是将匹配的过程转化为删除主串中字符使得与字串匹配。

当出现重复的字符时,出现的两种情况都需要保存,所以是上一行的两个元素相加。

从删除的角度来说,初始化就是以i-1为结尾的s可以随便删除元素,出现空字符串的个数,此时两个子串长度都是0,所以肯定是匹配的,也就是说,第一列初始化为1。

583 两个字符串的删除操作

这题与115 不同的子序列的差别在于两个字符串都是可以删除的,没有想出怎么推👉👈。题解给出了两种方法。

方法一:

考虑如何删除字符串的字符使得两个字符串达到相同的条件(与前一题的逻辑相同,但是感觉这个思路有一点难想)

按照动规五部曲操作一下:

  1. 定义动规的数组

    二维数组,数组的大小为(word1.size() + 1) * (word2.size() + 1);

  2. 递推公式的推导

    可以简单分为两种情况

    • 当dp[i][j]对应的两个字母相同时,表示此时是不用删字母的

      1
      dp[i][j] = dp[i - 1][j - 1]
    • 当dp[i][j]对应的两个字母不同时,表示我们需要删一个字母了,选择最小的

      1
      dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2)
  3. dp数组的初始化

    行和列是相似的,所以这里就考虑行了

    当行下标为i时,表示此时需要删i个字符,两个才能相同(因为另一个字符串是空的)

方法二:

逆向思考,这一题可以先求两个字符串的最长公共子序列,然后求差就可以得到需要删除多少个字符了。

72 编辑距离

按照五部曲推导一下

  1. dp数组为二维数组

  2. 递推公式

    • word1[j - 1] == word2[i - 1]

      1
      dp[i][j] = dp[i - 1][j - 1];
    • 当不相同时,我们有三种操作手段,分别是增、删、改,去其中的极小值

      1
      2
      3
      4
      dp[i][j] = min({dp[i - 1][j] + 1,  // 删除操作
      dp[i][j - 1] + 1, // 插入操作
      dp[i - 1][j - 1] + 1}); // 替换操作
      }
  3. 初始化

    行和列是相似的,所以这里就考虑行了

    当行下标为i时,表示此时需要删i个字符,两个才能相同(因为另一个字符串是空的)

647 回文子串

方法一:暴力解法

三重循环

方法二:双指针法

分辨计算一个字符作为中间点和两个字符作为中间点的情况,向两边扩散,如果相同的话就是回文子串。

方法三:动态规划

这里的dp数组的定义就想不到,竟然是bool类型的。。。。

很难想到,这个方法,遍历顺序还是得反着来的。

516 最长回文子序列

这里的子序列是可以不连续的!好像只能使用dp的方法操作了。

按照dp五部曲:

  1. dp数组的含义

    dp[i][j]表示第i-j个字符范围的回文子序列长度

  2. 递推公式

    • s[i] == s[j]

      1
      s[i][j] = s[i + 1][j - 1] + 2;
    • s[i] != s[j]

      此时表示不能同时加入两个字符,只能考虑加入一个,那么就加入有最长子序列的那一个。

      1
      dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  3. dp数组初始化(一个star,两个star,triple star)

    考虑当i == j时,此时的最长回文子序列是为1的,所以需要初始化为1。

  4. 遍历顺序

    dp[i][j]的推导,来自左,左下,下三个方向的数值,所以需要从左到右,从下到上进行推导。

整个流程感觉是很清晰,但是回顾一下竟然能实现这个算法,还是神奇!


代码随想录一刷笔记_动态规划(下)
http://example.com/2024/12/09/code-9-DP-2/
作者
Poivre
发布于
2024年12月9日
许可协议