My Muri Life

切换主题

本页目录

最长序列篇 ​

最长递增子序列 ​

300. 最长递增子序列

  • 状态定义：dp[i] = x，表示以nums[i]结尾的最长递增子序列的长度为x；
  • base case：dp[i] = 1；
  • 状态转移方程：dp[i] = Math.max(dp[i], dp[j] + 1)。
JavaScript
const lengthOfLIS = nums => {
  const len = nums.length
  const dp = Array(len).fill(1)
  let max = 1
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
        max = Math.max(max, dp[i])
      }
    }
  }
  return max
}

时间复杂度：O(n^2)；空间复杂度：O(n)。

最长公共子序列 ​

剑指 Offer II 095. 最长公共子序列

  • 状态定义：dp[i][j] = x，表示s1的前i个字符和s2的前j个字符之间最长公共子序列的长度为x；
  • base case：dp[i][0] = dp[0][j] = 0；
  • 状态转移方程：
    • 若s1.charAt(i-1) === s2.charAt(j-1)，则dp[i][j] = dp[i - 1][j - 1] + 1；
    • 若s1.charAt(i-1) !== s2.charAt(j-1)，则dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。
JavaScript
const longestCommonSubsequence = (s1, s2) => {
  const [m, n] = [s1.length, s2.length]
  const dp = Array(m + 1).fill(0).map(_ => Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (j = 1; j <= n; j++) {
      if (s1.charAt(i - 1) === s2.charAt(j - 1)) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[m][n]
}

时间复杂度：O(mn)；空间复杂度：O(mn)。

最长回文子序列 ​

516. 最长回文子序列

  • 状态定义：dp[i][j] = x，表示字符串中从s[i]至s[j]之间的最长回文子序列；
  • base case：dp[i][i] = 1，单字符也是回文；
  • 状态转移方程：
    • 若s.charAt(i) === s.charAt(j)，则dp[i][j] = dp[i + 1][j - 1] + 2；
    • 若s.charAt(i) !== s.charAt(j)，则dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])。
JavaScript
const longestPalindromeSubseq = s => {
  const len = s.length
  const dp = Array(len).fill(0).map(_ => Array(len).fill(0))
  for (let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < len; 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][len - 1]
}
// 方法二：反转字符串，然后求反转串和原串的LCS即可！！！

时间复杂度：O(n^2)；空间复杂度：O(n^2)。