【刷题DAY54】392, 115.md

发表于 | 分类于

392. 判断子序列

题目链接：https://leetcode.cn/problems/is-subsequence/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 和1143相似，判断s是否为t的子序列
  • dp[i][j] 以s[i-1]结尾、t[j-1]结尾的子序列长度 s不动 t动
  • if s[i-1] == t[j-1] dp[i][j] = dp[i-1][j - 1] + 1
  • if s[i-1] != t[j-1] dp[i][j] = dp[i][j - 1]
  • dp[0][j] = 0 dp[i][0] = 0

0x5 今日收获，记录一下自己的学习时长

  • 1h

115. 不同的子序列

题目链接：https://leetcode.cn/problems/distinct-subsequences/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 求 s 中有多少个 t
  • dp[i][j] 以s[i-1] 结尾的字符串 有dp[i][j]种方案 得到以t[j-1]结尾的字符串
  • if s[i-1] == t[j-1]
  • dp[i-j]
  • 用s[i - 1]来匹配 ？不需要考虑当前s子串和t子串的最后一位字母？ dp[i - 1][j - 1] s[0]…s[i-2] 中有多少个t[0]…t[j-2] 再加上新的s[i-1] t[j-1]就是了 不太好理解
  • 不用s[i - 1]来匹配，个数为dp[i - 1][j] s[0]…s[i-2] 中有多少个t[0]…t[j-1]
  • dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
  • if s[i-1] != t[j-1]
  • dp[i][j] = dp[i - 1][j]
  • dp[i][0] 为 1 dp[0][j] 为0

0x5 今日收获，记录一下自己的学习时长

  • 1.5h

总结

  • 判断子序列
  • 不同的子序列

复习

  • day31
    • 贪心
      • 分发饼干
      • 摆动序列
      • 最大子序和

待重点复习

392, 115, 376