当前位置: 首页 > news >正文

代码随想录——最长回文子序列(Leetcode 516)

题目链接
在这里插入图片描述

我的题解(动态规划)

思路:

    1. 确定状态 dp[i][j]
      dp[i][j] 表示:字符串 s 中从索引 ij 的子串中最长回文子序列的长度
    1. 确定状态转移方程
    • 如果 s[i] == s[j],则 dp[i][j] = dp[i + 1][j - 1] + 2
      • 这是因为 s[i]s[j] 可以作为最长回文子序列的一部分,并且 dp[i + 1][j - 1]s[i+1...j-1] 的最长回文子序列长度。
    • 如果 s[i] != s[j],则 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
      • 这是因为最长回文子序列要么在子串 s[i+1...j] 中,要么在子串 s[i...j-1] 中。
    1. 确定边界条件
      对于所有 idp[i][i] = 1。这是因为任何单个字符都是一个长度为 1 的回文子序列。
    1. 确定计算顺序
      计算顺序决定了动态规划数组 dp 的填充顺序。在这个问题中,我们需要按照子问题的规模从小到大来填充 dp 数组:
      s.length() - 1 开始向下遍历,然后对于每个 i,从 i + 1 开始向右遍历。
    1. 确定最终答案
      最终答案是 dp[0][s.length() - 1],它表示整个字符串 s 中的最长回文子序列的长度。
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];for (int i = 0; i < s.length(); i++){dp[i][i] = 1;}for(int i = s.length() - 1; i >= 0; i--){for(int j = i + 1; j < s.length(); j++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i + 1][j - 1] + 2;}else{dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.length() - 1];}
}

http://www.mrgr.cn/news/16276.html

相关文章:

  • 嵌入式全栈开发学习笔记---Linux系统编程(进程间通信)
  • 新进程的加载与创建
  • ZYNQ LWIP TCP学习
  • 四款远程控制分享!你pick哪一款?
  • 美容院拓客营销门店管理小程序渠道进行
  • LeetCode 热题100-9 找到字符串中所有字母异位词
  • 版本管理工具 Git 的下载安装及使用
  • 网络安全 加密编码进制
  • 鸿蒙启动框架配置文件(StartUpTask)
  • 【初阶C++篇】~ C++入门
  • Lua 代码编码规范
  • 一刷代码随想录(图论10)
  • 高级java每日一道面试题-2024年8月31日-框架篇[Spring篇]-你对Spring事务传播机制了解多少?
  • uboot
  • 第 20 章 DOM 进阶
  • Spring Boot 中 AOP 的实用举例
  • Vue——认识day06_class与style绑定
  • 常见框架报错信息
  • Java基础 - 12 - 多线程
  • 点点数据JS逆向:k值加密扣webpack代码和纯算实现