算法设计博文：动态规划（IV） about durant35.github.io

[Durant35]

DP习题 6.7 动态规划解答思路

http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

• dp[i][j]：[i, j] 区间内字符串的最长回文子序列
• 递推公式：
  • if (s[i] == s[j])：dp[i][j] 可以在 dp[i + 1][j - 1] 的基础上增加两个回文子序列长度
  • if (s[i] != s[j])：max(dp[i + 1][j], dp[i][j - 1])，去掉i或j其中的一个字符，然后比较两种情况下所剩的字符串哪个回文子序列长

[Durant35]

DP习题 6.7 直接递归解答思路

http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

• Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1].
• If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
  Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

[Durant35]

最长公共子序列

• 子序列 sub sequence问题，例：最长公共子序列，[LeetCode] Distinct Subsequences(求子序列个数)
• [LeetCode] Distinct Subsequences题解

跟着编程之美学算法——最长公共子序列

[Durant35]

最长递增子序列

P157 P196

300. Longest Increasing Subsequence

• [Lintcode] Longest Increasing Subsequence 最长上升序列
• 跟着编程之美学算法——最长递增子序列
• 最长上升子序列 LIS(Longest Increasing Subsequence)

[Durant35]

最长递增子序列

• 算法设计与分析[0010] Longest Increasing Subsequence（最长递增子序列）

最长公共子序列

• 最长公共子序列 #12

最长回文子序列

• 最长回文子序列 #13