LeetCode-Notes
  • Introduction
  • Records of Practice
  • 关于Github 不支持密码问题
  • 面试题
    • 搜索广告
    • 多模态大模型
    • 刷题记录
  • 算法代码实现
  • Python
    • Python 笔记
  • Spark
    • PySpark
    • Spark Issues
    • Spark调优笔记
  • FeatureEngineering
    • Feature Cleaning
    • Feature Selection
    • Feature Transformation
    • Feature Crossing
  • Recommendation Algorithm
    • Recall-and-PreRank
      • Non-Negative Matrix Fatorization(NMF)
      • Fatorization Machine(FM)
      • User-base/Item-base实现
      • 多路召回实现
    • Ranking
      • NeuralFM
      • DeepFM
      • Deep&Cross network (DCN)
    • DeepLearning-Basic
      • Attention
      • Dropout
      • Batch Norm
  • Machine Learning
    • XGBoost
    • Cross Entropy Loss
    • Other models
  • Graph Neural Network
    • GNN-1-Basic
  • Big Data
    • Reservoir Sampling
  • SQL
    • SQL and PySpark functions
    • Query Film Infomation
    • Create, Insert and Alter Actor Table
    • Manage Employment Data
    • Manage Employment Data -2
  • DataStructure
    • Searching
      • Find power
      • 2 Sum All Pair II
      • Two Sum
      • Search in Rotate Array
      • Search In Shifted Sorted Array II
      • Search in 2D array
      • Three Sum with duplicated values
      • Median of Two Sorted Arrays
    • Array
      • Longest Consecutive Subarray
      • Merge Two Array in-place
      • Trapping water
      • Rotate matrix
    • Sorting
      • Merge intervals
      • 排序
      • 最小的k个数
      • Find TopK largest- QuickSelect快速选择 method
      • MergeSort Linkedlist
      • 第K大元素
    • LinkedList
      • Reverse LinkedList I
      • Reverse K-group linked list
      • Detect Start of Cycle
      • HasCycle
      • DetectCycle II
      • 链表的共同节点
      • 链表中倒数第k个节点
      • 删除链表倒数第k个节点
      • 合并两个链表
      • 在排序数组中查找元素的第一个和最后一个位置
      • 删除链表里面重复的元素-1
    • Tree
      • Find Tree height (general iteration method)
      • Check BST and Check CompleteTree
      • ZigZag Order traversal
      • Binary Tree diameter I
      • Maximum Path Sum Binary Tree
      • Maximum Path Sum Binary Tree II
      • Binary Tree Path Sum To Target III
      • Tree diameter 树的直径II
      • Tree ReConstruction
      • Check if B is Subtree of A
      • The Kth smallest in Binary Search Tree
      • 打印Tree的右视图
      • 二叉搜索树的后序遍历序列
      • 重建二叉树
      • 判断二叉树是否对称
      • Path Sum to Target in Binary Tree
      • Tree-PreOrder-InOrder-PostOrder
    • Heap&Queue
      • Top-K smallest
      • 滑动窗口最大值
      • Find the K-Largest
    • 合并k个已排序的链表
    • String
      • Reverse String
      • 最长不含重复字符的子字符串
      • 最长回文串
      • 最长回文子序列-DP
    • DFS/BFS
      • Number of island
      • Number of Provinces
      • All Permutations of Subsets without duplication
      • All Permutations of Subsets with duplication
      • Combinations Of Coins
      • All Subset I (without fixing size of subset, without order, without duplication)
      • All Subset of K size without duplication II
      • All Subset of K size III (with duplication without considering order)
      • All Permutation II (with duplication and consider order)
      • Factor Combination-质数分解
    • DynamicProgramming
      • DP-解题过程
      • Find Continuous Sequence Sum to Target
      • 1800. Maximum Ascending Subarray Sum
      • NC91 最长上升子序列
      • 查找string的编码方式个数
      • Maximum Product
      • Longest Common Substring
      • Longest Common Substring-II
      • minEditCost
      • Backpack I
      • Array Hopper I
      • Minimum distance between strings
      • 最大正方形
  • Big Data Algorithms
    • Big Data Processing Algorithms
      • Reservior Sampling
      • Shuffle
      • MapReduce
      • Bloom Filter
      • BitMap
      • Heap For Big Data
Powered by GitBook
On this page

Was this helpful?

  1. DataStructure
  2. String

最长回文子序列-DP

Medium; DP; String

Previous最长回文串NextDFS/BFS

Last updated 4 years ago

Was this helpful?

1. Link

这题考虑 substring的顺序,不能改变顺序来得到回文数

2. 题目

给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入:

"bbbab" 输出:

4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:

"cbbd" 输出:

2

3. 题目

  1. idea: DP

  2. dp[i][j]: 从string char s[i]到s[j]的最长回文数

  3. 当i == j , dp[i][j] =0 只有一个char

  4. 当 i!=j, s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2 这里的2是考虑char s[i]和s[j]

  5. 当 s[i] != s[j], dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 分别把substring的头尾加到中间的substring然后看两者最大的长度

  6. 遍历时候,把string pointer i 从后面遍历到前面, 查找 substring i 到 len(s)-1 之间的substring

  7. Time : O(n^2), Space:O(n^2)

4. Coding

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #
        #idea: DP
        # state: dp[i] = max length of palindrome between char i and the last char in string
        # transition function:
        # if we have a substring   s[i] s[i+1]...s[j]
        # 如果 s[i] == s[j], 那么dp[i] = max length of palindrom from s[i+1] to s[j-1] + 2 
        # 这里的2 代表 s[i], s[j]
        # 否则dp[i] 不变,依旧是之前找到的考虑s[i]的回文数的长度
        #dp[0] = 1
        # dp[1] = max(dp[1],)
        #
        # dp= [0]*len(s)
        
        # for i in range(len(s)):
        #     dp[i] = 1
        #     max_len = 0
        #     for j in range(i-1, -1, -1):
        #         tmp = dp[j]
        #         if s[i] == s[j]:
        #             dp[j] = max_len + 2
        #         max_len = max(tmp, max_len)
        # return max(dp)
            
        #
        #idea2: 2D-DP
        # state: dp[i][j] = 第i个char到第j个char的最长回文数长度
        # 而 如果第s[i] == s[j] 那么  dp[i][j] = dp[i+1][j-1] + 2 (加上 s[i], s[j]两个)
        # 如果s[i]!=s[j], 那么 dp[i][j]= max(dp[i+1][j],dp[i][j-1]),把s[i], s[j]分别加入回文数看哪个更长
        # 所以 dp[i][i] =1
        # row, col = string
        # 1. iterate s in i 
        #       iterate s in j
        #            when i != j and s[i] == s[j]-> 找到回文数的相同char
        #

        dp = [[0]*len(s) for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        max_len = 0
        for i in range(len(s)-1, -1,-1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]+2
                else:
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])
                max_len = max(max_len, dp[i][j])
        return dp[0][-1]

                    

来源:力扣(LeetCode) 链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

https://leetcode-cn.com/problems/longest-palindromic-subsequence
力扣
Logo