516. Longest Palindrome Subsequence
动态规划,dynamic programming:将一个问题拆成几个子问题,分别求解这些子问题,即可推断出大问题的解。
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)).
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
# Base Case 1: If there is
# only 1 character
if s == s[::-1]:
return len(s)
n = len(s)
dp = [0 for j in xrange(n)]
dp[n-1] = 1
for i in xrange(n-1, -1, -1): # can actually start with n-2...
newdp = dp[:]
newdp[i] = 1
for j in xrange(i+1, n):
if s[i] == s[j]:
newdp[j] = 2 + dp[j-1]
else:
newdp[j] = max(dp[j], newdp[j-1])
dp = newdp
return dp[n-1]
参考链接:
https://www.ideserve.co.in/learn/longest-palindromic-subsequence
请多多指教。
文章标题:516. Longest Palindrome Subsequence
本文作者:顺强
发布时间:2018-02-01, 23:59:00
原始链接:http://shunqiang.ml/leetcode-516-longest-palindrome-subsequence/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。