【刷题DAY56】647, 516.md

发表于 | 分类于

647. 回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/

0x1 看到题目的第一想法

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

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

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

1
2
3
4
5
# dp[i][j] 区间[i,j]左闭右闭的子字符串是否为回文
# if s[i] != s[j] dp[i][j] = false
# if s[i] == s[j] if j == i:true if j == i+1:true else  if dp[i+1][j-1] true else False
# dp 为false
# !!注意遍历顺序，依赖于左下角，所以要从下往上、从左往右遍历

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

  • 1h

516. 最长回文子序列

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

0x1 看到题目的第一想法

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

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

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

1
2
3
4
# dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
# if s[i] == s[j] dp[i][j] = dp[i+1][j-1]+2
# if s[i] != s[j] dp[i][j] = max(dp[i+1][j], dp[i][j-1])
# 初始化 if i == j dp[i][j] == 1 其余为0

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

  • 1h

总结

  • dp五步法
  • 背包问题
  • 打家劫舍系列
  • 股票系列
  • 子序列系列

复习

  • day33
    • 贪心
      • 分发糖果
        • 需要两个维度考虑，每次从一个维度考虑

待重点复习

647, 516, 135